Leetcode 670. 最大交换

1.题目描述

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

1. 给定数字的范围是 $[0,10^8]$

2.思路分析

2.1 暴力解法

由于对于整数 $num $的十进制数字位长最长为 $8$ 位，任意两个数字交换一次最多有 $28$ 种不同的交换方法，因此可以尝试遍历所有可能的数字交换方法即可，并找到交换后的最大数字即可。

• 将数字存储为长度为 $n$ 的列表，其中 $n$ 为整数 $num$ 的十进制位数的长度。对于位置为 $(i,j)$ 的每个候选交换，交换数字并记录组成的新数字是否大于当前答案；
• 对于前导零的问题，也不需要特殊处理。
• 由于数字只有 $8$ 位，所以不必考虑交换后溢出的风险；

2.2 贪心

找每位右侧的最大值然后贪心地从高位向低位考察, 当有数值相同的多个大数时，选择低位的数字

比如86599, 交换最高位和最低位的收益(96598)是大于交换最高位和次低位的收益的(96589)

• 先把数字拆分成一位位的
• 从低位向高位遍历, 得到每位的右侧(更低位方向)最大数字, 这里的右侧包含当前位置, 如果严格右侧的最大值和当前位置的值相同那么取右侧更低位的作为结果, 记录每位右侧更大的数的下标
• 从高位向低位遍历, 如果有某位的右侧最大数字大于当前, 那么交换这两个数字并停止遍历
• 把拆开的各位拼接回答案即可

3.代码实现

3.1 暴力解法

class Solution:
    def maximumSwap(self, num: int) -> int:
        ans = num
        s = list(str(num))
        for i in range(len(s)):
            for j in range(i):
                # 交换i,j的位置
                s[i], s[j] = s[j], s[i]
                ans = max(ans, int(''.join(s)))
                # 还原s数组,方便后续比较
                s[i], s[j] = s[j], s[i]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析:

• 时间复杂度:$O(lo{g}^{2}num)$，其中整数 $\text{num}$ 为给定的数字。$\text{num}$ 转换为十进制数，有 $O(\log \text{num})$个数字，一共有 $O({\log }^2\text{num})$种不同的交换方法。
• 空间复杂度:$O(lognum)$，其中整数 $\text{num}$ 为给定的数字。$\text{num}$ 转换为十进制数，有 $O(\log \text{num})$O 个数字，需要保存 $\text{num}$ 所有的数字。

3.2 贪心算法

class Solution:
    def maximumSwap(self, num: int) -> int:
        nums = []
        # nums数组中高位在数组右边
        while num:
            nums.append(num % 10)
            num //= 10
        print(nums)

        # 建立索引
        right_max = [i for i in range(len(nums))]
        print(right_max)
        # 从低位到高位遍历,找到每位的右侧最大数字,记录的是下标
        for i in range(1, len(nums)):
            if nums[right_max[i - 1]] >= nums[right_max[i]]:
                right_max[i] = right_max[i - 1]

        # 从高位向低位遍历,
        for i in range(len(right_max)-1, -1, -1):
            if nums[right_max[i]] > nums[i]:
                nums[i], nums[right_max[i]] = nums[right_max[i]], nums[i]
                break

        ans = 0
        for i in range(len(nums)-1, -1, -1):
            ans *= 10
            ans += nums[i]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

复杂度分析:

• 时间复杂度:$O(lognum)$，其中整数 $\text{num}$ 为给定的数字。
• 空间复杂度:$O(lognum)$，其中整数 $\text{num}$ 为给定的数字。

参考:
1.https://leetcode.cn/problems/maximum-swap/solution/zui-da-jiao-huan-by-leetcode-solution-lnd5/
2.https://leetcode.cn/problems/maximum-swap/solution/by-isuxiz-d3sh/