[LeetCode] 670. Maximum Swap

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:
Input: num = 9973
Output: 9973
Explanation: No swap.

Constraints:
0 <= num <= 108

最大交换。

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。

思路

基本思路是贪心。将 input 数字转成 char array，再创建一个叫做 bucket 的数组，长度为 10，记录每个数字在 char array 中最后出现的下标。遍历 char array，把每个不同数字最后出现的下标记录好。

再次遍历 char array，对于 i 位置上的数字 d，我们从 9 到 0 看看是否有一个比 d 更大的数字，如果有，我们再看看这个更大的数字最后一次出现的下标是否大于 i，如果是，则将位置 i 上的这个数字与那个更大的数字交换位置。最后，将 char array 转成数字，返回即可。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();
        int[] last = new int[10];
        // 记录每个不同数字最后一次出现的位置
        for (int i = 0; i < digits.length; i++) {
            last[digits[i] - '0'] = i;
        }

        // 再次扫描
		// 对于每个数字，看是否有一个比当前这个数字更大的数字在右边，从9开始看
		// 若有，就swap过来
        for (int i = 0; i < digits.length; i++) {
            for (int j = 9; j > digits[i] - '0'; j--) {
                if (i < last[j]) {
                    char temp = digits[i];
                    digits[i] = digits[last[j]];
                    digits[last[j]] = temp;
                    return Integer.valueOf(new String(digits));
                }
            }
        }
        return num;
    }
}