最多 K 次交换相邻数位后得到的最小整数

难度: Hard

给你一个字符串 num 和一个整数 k 。其中，num 表示一个很大的整数，字符串中的每个字符依次对应整数上的各个数位。

你可以交换这个整数相邻数位的数字最多 k 次。

请你返回你能得到的最小整数，并以字符串形式返回。

示例 1：

输入：num = "4321", k = 4
输出："1342"
解释：4321 通过 4 次交换相邻数位得到最小整数的步骤如上图所示。

示例 2：

输入：num = "100", k = 1
输出："010"
解释：输出可以包含前导 0 ，但输入保证不会有前导 0 。

示例 3：

输入：num = "36789", k = 1000
输出："36789"
解释：不需要做任何交换。

示例 4：

输入：num = "22", k = 22
输出："22"

示例 5：

输入：num = "9438957234785635408", k = 23
输出："0345989723478563548"

提示：

1 <= num.length <= 30000
num 只包含数字且不含有 前导 0 。
1 <= k <= 10^9

Submission

运行时间: 136 ms

内存: 18.8 MB

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        res = []
        while k > 0 and num:
            for i in range(10):
                ch = str(i)
                idx = num.find(ch)
                if idx < 0:
                    continue
                if idx <= k:
                    res.append(ch)
                    num = num[:idx] + num[idx + 1 :]
                    k -= idx
                    break
        return "".join(res) + num

Explain

此题解采用贪心算法的思路，目标是尽可能将更小的数字移动到字符串的前面。算法遍历数字0到9，对于每个数字，查找其在字符串`num`中的第一个出现位置。如果该位置在允许的交换次数`k`内，那么就将该数字移动到结果字符串`res`的末尾，并从原字符串中删除该数字，同时减少`k`的值。这个过程一直重复，直到没有交换次数或字符串处理完毕。最后，将剩余的`num`直接附加在`res`后面，得到最终结果。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        res = []  # 结果字符串数组
        while k > 0 and num:  # 当还有交换次数且num非空时执行
            for i in range(10):  # 从数字0到9尝试
                ch = str(i)
                idx = num.find(ch)  # 寻找数字在字符串中的位置
                if idx < 0:  # 如果数字不在字符串中，继续下一个数字
                    continue
                if idx <= k:  # 如果位置在可交换范围内
                    res.append(ch)  # 添加到结果数组
                    num = num[:idx] + num[idx + 1 :]  # 从原字符串中删除该数字
                    k -= idx  # 减少可用的交换次数
                    break  # 找到最小的可交换数字后跳出循环
        return ''.join(res) + num  # 将结果数组转换为字符串并加上剩余的num

Explore

在题解中，从数字0到9的顺序寻找是基于贪心算法的思路，目的是尽早在结果中放置较小的数字。贪心策略在这类问题中通常表现良好，因为较小的数字出现在结果的前面可以显著降低整体数值。虽然这个方法可能不会在所有情况下保证全局最优解，但它是一个有效的启发式策略，通常能产生接近最优的结果。

如果某个数字的位置超出了剩余的交换次数`k`，那么这个数字不能移动到当前结果字符串的末尾。在这种情况下，算法会继续检查下一个数字。这是因为只有当数字的位置在`k`的范围内时，才能通过相邻交换将其移动到结果字符串的前面。超出`k`范围的数字在当前步骤中不能被移动，故继续寻找其他可能的数字。

在找到一个可交换的数字后立即跳出循环是因为已经找到了当前可以移动的最小数字。由于从0到9的顺序寻找，首次找到的可交换数字即是当前可用的最小数字。继续寻找可能更近的其他数字可能会导致结果不是最小可能值，因为已经跳过了一个更小的确定可交换的数字。

题解中的方法基于贪心策略，它试图确保每次操作都得到当前能够达到的局部最优解。对于连续多个相同的数字，算法会将每个数字视作独立的考虑对象。如果这些相同的数字中的某个可以在允许的交换次数`k`内移动到前面，则会进行移动。这个方法在大多数情况下是有效的，但在某些特定配置下可能不会生成全局最小的整数，因此它没有考虑所有可能的情况，而是依赖于贪心策略来近似最佳解。