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++) {
            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;
    }
}

class Solution {
    public int maximumSwap(int num) {
        String numStr = String.valueOf(num);
        int len = numStr.length();
        char[] sorted = numStr.toCharArray();
        Arrays.sort(sorted);
        String numStrSorted = new String(sorted);

        for (int i = 0; i < len; i++) {
            char numC = numStr.charAt(i);
            char sortedC = numStrSorted.charAt(len - i - 1);

            if (numC != sortedC) {
                return swap(numStr, i, sortedC);
            }
        }

        return num;
    }

    private int swap(String numStr, int start, char maxNum) {
        char[] numArr = numStr.toCharArray();
        int maxIndex = start;
        for (int i = start; i < numArr.length; i++) {
            if (numArr[i] == maxNum) {
                maxIndex = i;
            }
        }

        numArr[maxIndex] = numArr[start];
        numArr[start] = maxNum;
        return Integer.parseInt(new String(numArr));
    }
}