Maximum Swap

https://leetcode.com/problems/maximum-swap/description/

Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.

Example 1:

Input: 2736

Output: 7236

Explanation: Swap the number 2 and the number 7.

Example 2:

Input: 9973

Output: 9973

Explanation: No swap.

Thoughts

只允许swap两个数字, 让它能达到所有可能swap/不swap中最大. 由于都是正数, 那么让前面位数尽量大, 如果能swap, 意味着从前数第i位后面有比nums[i]更大的数且应挑选其中最大的. 因此用一个数组存储0~9每个数字在nums中最后出现的位置, 再从左往后遍历nums, 对于nums[i]从大往小搜索比nums[i]的位置靠后的, 搜到了swap返回即可.

Code

class Solution {
    public int maximumSwap(int num) {
        char[] nums = Integer.toString(num).toCharArray();
        int[] lastShown = new int[10];
        for (int i = 0; i < nums.length; i++) {
            lastShown[nums[i] - '0'] = i;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 9; j > nums[i] - '0'; j--) {
                if (lastShown[j] > i) {
                    swap(nums, i, lastShown[j]);
                    return Integer.valueOf(new String(nums));
                }
            }
        }

        return num;
    }

    private void swap(char[] nums, int i, int j) {
        char tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Analysis

时间复杂度O(N).