LeetCode 题解工作台
邻位交换的最小次数
给你一个表示大整数的字符串 num ，和一个整数 k 。 如果某个整数是 num 中各位数字的一个 排列 且它的 值大于 num ，则称这个整数为 妙数 。可能存在很多妙数，但是只需要关注 值最小 的那些。 例如， num = "5489355142" ： 第 1 个最小妙数是 "548935521…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们可以调用 次 `next_permutation` 函数，得到第 个最小妙数 。 接下来，我们只需要计算 需要经过多少次交换才能变成 即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个表示大整数的字符串 num ，和一个整数 k 。
如果某个整数是 num 中各位数字的一个 排列 且它的 值大于 num ，则称这个整数为 妙数 。可能存在很多妙数，但是只需要关注 值最小 的那些。
- 例如，
num = "5489355142"：- 第 1 个最小妙数是
"5489355214" - 第 2 个最小妙数是
"5489355241" - 第 3 个最小妙数是
"5489355412" - 第 4 个最小妙数是
"5489355421"
- 第 1 个最小妙数是
返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。
测试用例是按存在第 k 个最小妙数而生成的。
示例 1：
输入：num = "5489355142", k = 4 输出：2 解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字： - 交换下标 7 和下标 8 对应的位："5489355142" -> "5489355412" - 交换下标 8 和下标 9 对应的位："5489355412" -> "5489355421"
示例 2：
输入：num = "11112", k = 4 输出：4 解释：第 4 个最小妙数是 "21111" ，要想得到这个数字： - 交换下标 3 和下标 4 对应的位："11112" -> "11121" - 交换下标 2 和下标 3 对应的位："11121" -> "11211" - 交换下标 1 和下标 2 对应的位："11211" -> "12111" - 交换下标 0 和下标 1 对应的位："12111" -> "21111"
示例 3：
输入：num = "00123", k = 1 输出：1 解释：第 1 个最小妙数是 "00132" ，要想得到这个数字： - 交换下标 3 和下标 4 对应的位："00123" -> "00132"
提示：
2 <= num.length <= 10001 <= k <= 1000num仅由数字组成
解题思路
方法一：求下一个排列 + 逆序对
我们可以调用 次 next_permutation 函数，得到第 个最小妙数 。
接下来，我们只需要计算 需要经过多少次交换才能变成 即可。
我们先考虑一个简单的情况，即 中的数字都不相同。在这种情况下，我们可以直接把 中的数字字符映射为下标。例如 等于 "54893"，而 等于 "98345"。我们将 中的每个数字映射为下标，即：
那么 中的每个数字映射为下标，就是 "32410"。这样，将 变成 所需要的交换次数，就等于 映射后的下标数组的逆序对数。
如果 中存在相同的数字，那么我们可以使用一个数组 来记录每个数字出现的下标，其中 表示数字 出现的下标列表。为了使得交换次数尽可能少，在将 映射为下标数组时，我们只需要按顺序贪心地选择 中对应数字的下标即可。
最后，我们可以直接使用双重循环来计算逆序对数，也可以使用树状数组来优化。
时间复杂度 ，空间复杂度 。其中 是 的长度。
class Solution:
def getMinSwaps(self, num: str, k: int) -> int:
def next_permutation(nums: List[str]) -> bool:
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i < 0:
return False
j = n - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1 : n] = nums[i + 1 : n][::-1]
return True
s = list(num)
for _ in range(k):
next_permutation(s)
d = [[] for _ in range(10)]
idx = [0] * 10
n = len(s)
for i, c in enumerate(num):
j = ord(c) - ord("0")
d[j].append(i)
arr = [0] * n
for i, c in enumerate(s):
j = ord(c) - ord("0")
arr[i] = d[j][idx[j]]
idx[j] += 1
return sum(arr[j] > arr[i] for i in range(n) for j in range(i))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate identify the next permutation and apply it repeatedly?
- question_mark
Does the candidate understand the trade-offs between different strategies to minimize swaps?
- question_mark
Is the candidate able to optimize the process for finding the kth smallest permutation?
常见陷阱
外企场景- error
Not using the two-pointer technique efficiently, leading to unnecessary swaps.
- error
Failing to account for edge cases where the number contains repeated digits or leading zeros.
- error
Overcomplicating the problem by using a brute-force approach to generate permutations.
进阶变体
外企场景- arrow_right_alt
What if we had to find the mth smallest permutation instead of the kth?
- arrow_right_alt
What if the input number is extremely large, pushing the upper limit of constraints?
- arrow_right_alt
What if the digits were not confined to 0-9 but included other characters or symbols?