Java O(n^2) solution


  • 0
    F

    1 The left to swap should be as left as possible
    2 The right to swap should be as big as possible

      public int maximumSwap(int num) {
            if (num == 0) return 0;
            List<Integer> l = new ArrayList<>();
            while (num > 0) {
                l.add(num%10);
                num/=10;
            }
            for (int i = l.size()-1; i>= 0; --i) {
                int max = l.get(i), k = -1;
                for (int j = i-1; j >= 0; --j) {
                    if (l.get(j) >= max) {
                        max = l.get(j);
                        k = j;
                    }
                }
                if (max == l.get(i)) continue;
                int t = l.get(i);
                l.set(i, max);
                l.set(k, t);
                break;
            }
            for (int i = l.size()-1; i >= 0; --i) {
                num = num * 10 + l.get(i);
            }
            return num;
        }
    

Log in to reply
 

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