<div>
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:
<pre>Input: num = 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. </pre>
Example 2:
<pre>Input: num = 9973 Output: 9973 Explanation: No swap. </pre>
Constraints:
0 <= num <= 10<sup>8</sup>
</div>
题目大意：
给定一个数，最多交换一位，使得这个数尽可能最大
解题思路：
类似于LeetCode 854 K-Similar Strings, 如2736， 求2后面最大的数为7，和7交换即为所求。这里有两个问题：
- 第一位可能已经是最大的数位，这样需要遍历每个数位，找到能交换的数位，若这个位在倒序排序后位置一样，表明此位不能交换。所以排序法的算法复杂度为n平方
- 若要优化就要采用bucket sort，因为数位是有限的。若后续数位有一个数比自己大，表示可交换。所以只要记录每个数位的位置，贪心法从9(最大)遍历到自己，若该位位置在自己之后，可交换
- 若不同数位上数值相同，应该记录其最后的位置，因为交换时候将小的尽量往后交换，越好越不重要，如2949, 2和最后的9交换得到最大的数
解题步骤：
N/A
注意事项：
- 内循环从9遍历到该位数值(不包括)
- buckets的key为字符串，注意整数和字符串互换，如buckets[str(j)], int(digits[i])
Python代码：
1
2
3
4
5
6
7
8
9def maximumSwap(self, num: int) -> int:
digits, buckets = str(num), collections.defaultdict(int)
for i, digit in enumerate(digits):
buckets[digit] = i # use last position for same char
for i in range(len(digits)):
for j in range(9, int(digits[i]), -1): # remember to use int(digits[i]) not i
if buckets[str(j)] > i: # 2736, i = (2), j = (7) # remember to use str j
return int(digits[:i] + digits[buckets[str(j)]] + digits[i + 1:buckets[str(j)]] + digits[i] + digits[buckets[str(j)] + 1:])
return num
算法分析：
时间复杂度为O(9n)，空间复杂度O(n)
