Java O(n) Solution with Explanation


  • 0
    M
        public int maximumSwap(int num) {
            char[] digits = String.valueOf(num).toCharArray();
            int[] bucket = new int[10];
            final int LEN = digits.length;
            for(int i=0; i<LEN; i++){
                bucket[digits[i]-'0'] = i; // the last time the digit appears
            }
            for(int i=0; i<LEN; i++){
                for(int k=9; k>digits[i]-'0'; k--){ // current digit is smaller than k
                    if(bucket[k] > i) { // and k appears in the right position
                        char temp = digits[bucket[k]]; // swap k and current digit
                        digits[bucket[k]] = digits[i];
                        digits[i] = temp;
                        return Integer.parseInt(new String(digits));
                    }
                }
            }
            return num;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.