670. Maximum Swap

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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 <= 10^8$

Code

class Solution {
    public int maximumSwap(int num) {
        int[] dict = new int[10];
        char[] arr = String.valueOf(num).toCharArray();

        for (int i = 0; i < arr.length; i++) {
            // 这个数字的最后一个index
            dict[arr[i] - '0'] = i;
        }

        for (int i = 0; i < arr.length; i++) {
            int currNum = arr[i] - '0';
            // 比当前数大的数
            // 并且在当前数后边
            for (int k = 9; k > currNum; k--) {
                // index在当前数字之后
                if (dict[k] > i) {
                    char temp = arr[i];
                    arr[i] = arr[dict[k]];
                    arr[dict[k]] = temp;
                    return Integer.parseInt(new String(arr));
                }
            }
        }

        return num;
    }
}