LeetCode 670 Maximum Swap

LeetCode

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<sup>8</sup>

题目大意：

给定一个数，最多交换一位，使得这个数尽可能最大

解题思路：

类似于LeetCode 854 K-Similar Strings, 如2736， 求2后面最大的数为7，和7交换即为所求。这里有两个问题：

1. 第一位可能已经是最大的数位，这样需要遍历每个数位，找到能交换的数位，若这个位在倒序排序后位置一样，表明此位不能交换。所以排序法的算法复杂度为n平方
2. 若要优化就要采用bucket sort，因为数位是有限的。若后续数位有一个数比自己大，表示可交换。所以只要记录每个数位的位置，贪心法从9(最大)遍历到自己，若该位位置在自己之后，可交换
3. 若不同数位上数值相同，应该记录其最后的位置，因为交换时候将小的尽量往后交换，越好越不重要，如2949, 2和最后的9交换得到最大的数

解题步骤：

N/A

注意事项：

1. 内循环从9遍历到该位数值(不包括)
2. buckets的key为字符串，注意整数和字符串互换，如buckets[str(j)], int(digits[i])

Python代码：

def 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)