Leetcode679 Maximum Swap

Posted on In

题目描述

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:

1
2
3
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

Example 2:

1
2
3
Input: 9973
Output: 9973
Explanation: No swap.

Note:

The given number is in the range [0, 108]

解析

给定一个数字，允许其中某两位交换一次，求能生成的最大数字。

暴力法很好想到，先转换为字符串，从头开始遍历，对于第i个数，找[i + 1, n]里的最大的数字，交换下就行了，复杂度为(O^2)。

当然，我们可以用空间换时间，比如先遍历一边，用一个数组保留[i + 1, n]里的最大的数字和所在位置即可。

注意到，所有数字其实只有0-9这十种可能性，在上面想法的基础上，我们可以做进一步优化，也就是说用一个数组保留0-9最后出现的位置，然后循环的时候比较看看0-9有没有比num[i]大，且出现的位置在i之后的数，如果有交换即可，为什么要保留最后出现的位置？ 这是由于越如果交换，小的数字放得越后，整个数字就越大，本题说到底还是一个贪心算法的思路。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int maximumSwap(int num) {
    char[] str = Integer.toString(num).toCharArray();
    int[] last = new int[10];
    // 存储0-9最后出现的位置
    for(int i = 0; i < str.length; i++){
        last[str[i] - '0'] = i;
    }
    for(int i = 0 ; i < str.length; i++){
        for(int d = 9; d > -1; d--){
            //反向迭代，根据贪心的思路，如果找到，则交换后必然为最大值
            if(d > str[i] - '0' && last[d] > i){
                char tmp = str[i];
                str[i] = str[last[d]];
                str[last[d]] = tmp;
                return Integer.valueOf(new String(str));
            }
        }    
    }
    return num;  
}