LC.P670[最大交换]

方法一：选择排序(从后往前)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maximumSwap(int num) {
        char[] nums = String.valueOf(num).toCharArray();
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            int maxIndex = i;
            // 从后往前选择一个最大的，这个最大的离i越远越好，比如1993，1交换第二个9更优，所以j倒序遍历
            for (int j = n - 1; j >= i + 1; --j) {
                if (nums[j] > nums[maxIndex]) {
                    maxIndex = j;
                }
            }
            if (maxIndex != i) {
                char temp = nums[maxIndex];
                nums[maxIndex] = nums[i];
                nums[i] = temp;
                return Integer.parseInt(new String(nums));
            }
        }
        return num;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$

方法二：一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maximumSwap(int num) {
        char[] nums = Integer.toString(num).toCharArray();
        int n = nums.length, maxIndex = n - 1, p = -1, q = 0;
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            } else if (nums[i] < nums[maxIndex]) {
                p = i;
                q = maxIndex;
            }
        }
        // num 本身是降序
        if (p == -1) {
            return num;
        }
        char temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;
        return Integer.parseInt(new String(nums));
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$