题目描述
思路解析动画文字版
两步套路:先用「下一个排列」做 k 次求出第 k 个最小妙数(找拐点 i、找 j 交换、反转后缀);再用冒泡把 num 逐位对齐到目标、累加相邻交换次数(等于逆序对数)。下面每帧都在套它。
总览 · 先求目标再数代价：先看清画面。上面这排格子是 num 等于 1234,四位数字 1、2、3、4,下标 0 到 3。任务分两步:第一步反复求「下一个排列」3 次,拿到第 3 个最小妙数当目标;第二步再数从 1234 挪到那个目标,最少要几次相邻交换。右边面板先记第一步:已经求到第几个妙数、当前排列长什么样、这一步在做什么。
第 1 次下一排列 · 找拐点 i：求第 1 个最小妙数。从最右边往左看,找第一个「比它右邻小」的位置,这就是拐点。下标 3 是 4,它右边没有邻居;看下标 2 的 3,它右边是 4,3 小于 4,拐点就是它,i 等于 2,绿色标住。拐点意味着从这里开始往大调,能得到更大的排列。
第 1 次下一排列 · 找交换对象 j：找到拐点后,再从最右边往左找第一个「大于拐点数字 3」的位置,把它拿来和拐点换。下标 3 是 4,4 大于 3,正好,j 等于 3,蓝色标住。为什么找刚好大于它的?这样换过去,增幅最小,才是紧挨着的下一个更大排列。
第 1 次下一排列 · 交换 i 与 j：把拐点 i 等于 2 的 3,和 j 等于 3 的 4 交换。1234 就变成了 1243。现在前面变大了一点,但拐点后面那一段还得处理:交换完拐点后面可能不是最小顺序,要再收拾一下。
第 1 次下一排列 · 反转后缀得 1243：最后把拐点后面那一段整体反转,让后缀尽量小。这次拐点在下标 2,后缀只有下标 3 一位,反转以后还是它自己,所以结果就是 1243。这就是第 1 个最小妙数。右边面板记上:已求到第 1 个。接着求第 2 个。
第 2 次下一排列 · 找拐点 i：在 1243 上求下一个排列。还是从右往左找拐点。下标 2 是 4,它右邻是 3,4 大于 3,不是拐点,标红跳过;再看下标 1 的 2,右邻是 4,2 小于 4,拐点就是它,i 等于 1,绿色标住。
第 2 次下一排列 · 找交换对象 j：再从最右往左找第一个大于拐点数字 2 的位置。下标 3 是 3,3 大于 2,就是它,j 等于 3,蓝色标住。注意后缀 43 是递减的,从右边第一个大于 2 的必然是恰好比 2 大一点的那个,换过去增幅最小。
第 2 次下一排列 · 交换 i 与 j：把拐点下标 1 的 2 和下标 3 的 3 交换,1243 变成 1342。这时拐点后面是下标 2 和 3 的 4、2,还是从大到小排的,不是最小,得反转一下才是真正的下一个排列。
第 2 次下一排列 · 反转后缀得 1324：把拐点后面下标 2 到 3 的 42 整体反转成 24,1342 就变成了 1324。这一步很关键:反转前是 1342,直接用会跳过好几个更小的妙数;反转后的 1324 才是紧挨着 1243 的下一个。已求到第 2 个,再求第 3 个。
第 3 次下一排列 · 找拐点 i：在 1324 上求最后一次下一排列。从右往左找拐点:下标 2 是 2,右邻下标 3 是 4,2 小于 4,拐点立刻就是它,i 等于 2,绿色标住。这次拐点靠得很右,后面处理会很轻。
第 3 次下一排列 · 找交换对象 j：从最右往左找第一个大于拐点数字 2 的位置。下标 3 是 4,4 大于 2,就是它,j 等于 3,蓝色标住。拐点后面只有这一位,待会儿交换完基本就成了。
第 3 次下一排列 · 得目标 1342：把拐点下标 2 的 2 和下标 3 的 4 交换,1324 变成 1342。拐点后面只剩一位,反转它还是自己,所以直接就是结果。第 3 个最小妙数就是 1342,这正是我们要够到的目标串。第一步大功告成。
第二步开始 · 把 1234 挪成 1342：第二步换个目标记法。上面重新摆回原串 1234,右边面板改记第二步:目标串是 1342,已经对齐的前缀、以及累计交换了几次。规则是每次只能交换相邻两位。我们从左到右,一位一位把当前串对齐成目标,顺手把交换次数加起来。
对齐第 0 位 · 目标要 1：看目标第 0 位,要的是 1。当前串下标 0 正好就是 1,不用动,零次交换。绿色标住下标 0,它已经对齐好了。前缀「1」锁定,往后这一位不再碰。看第 1 位。
对齐第 1 位 · 目标要 3：目标第 1 位要的是 3。在当前串 1234 里,3 待在下标 2,可它该去下标 1。绿色标住这个 3,红色标下标 1,那是它的目的地。相邻交换只能一步步挪,所以要把 3 和它左边的 2 交换,往左顶一格。
交换 · 3 挪到下标 1：交换下标 1 和 2 的 2 和 3,当前串从 1234 变成 1324。3 顺利落到下标 1,和目标对上了。交换次数从 0 加到 1。绿色标住就位的 3。现在前缀「13」都对齐了,看第 2 位。
对齐第 2 位 · 目标要 4：目标第 2 位要的是 4。当前串 1324 里,4 待在下标 3,它该去下标 2。绿色标住这个 4,红色标下标 2 是目的地。同样用相邻交换,把 4 和它左边的 2 换一下,往左顶一格。
交换 · 4 挪到下标 2：交换下标 2 和 3 的 2 和 4,当前串从 1324 变成 1342。4 落到下标 2,对上目标。交换次数从 1 加到 2。绿色标住就位的 4。此时前缀「134」都对齐了,只剩最后一位。
对齐第 3 位 · 目标要 2：看目标最后一位,要的是 2。当前串 1342 的下标 3 已经是 2,自动就位,不用再换。绿色标住它。到这里当前串已经完全等于目标串 1342,交换次数停在 2。为什么最后一位总能自动对上?前三位都对齐了,剩下的那位没得选,一定也对。
完成 · 最小交换次数 = 2：收尾。当前串已经完全变成目标 1342,一路数下来:对齐 3 用了 1 次交换,对齐 4 又用了 1 次,一共 2 次。这就是把 1234 变成第 3 个最小妙数所需的最少相邻交换次数。整个过程分两步:先用下一个排列求出目标,再用冒泡对齐数出代价。
复核 · 交换次数等于逆序对数：再从另一个角度复核一遍。目标串 1342 的每一位,分别来自原串的下标 0、2、3、1。把这串下标 0、2、3、1 看成一个排列,数它有几对「前面的比后面的大」的逆序对:2 比 1 大是一对,3 比 1 大又是一对,一共 2 对。逆序对数恰好等于相邻交换的最小次数,这也是参考代码直接数逆序对的道理。
边界:00123 含前导零仍参与排列(答案 1);11112 里 2 跨 4 个 1 需 4 次;本节 1234、k=3 得目标 1342、答案 2。
面试重点:下一排列每次给紧邻的下一个更大排列,做 k 次即第 k 个妙数;相邻交换每次消一个逆序对、下界即逆序对数且可达;重复数字靠位置桶按出现顺序取以避免多造逆序对。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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))复杂度
- 时间：O(k·n + n²)，n 是数字位数,k 是题目给的次数。第一步做 k 次下一个排列,每次最多扫一遍串,是 O(k·n);第二步数逆序对用的是双重循环,两两比较,是 O(n²)。两段相加就是 O(k·n + n²)。数逆序对若换成树状数组可以降到 O(n log n),但参考解用的是直观的双重循环
- 空间：O(n)，按峰值算。额外开了 10 个桶合起来存 n 个下标、一个长度为 n 的位置数组、还有目标字符数组,都是和 n 同阶的,没有更大的结构。所以额外空间是线性的 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么连做 k 次「下一个排列」就能得到第 k 个最小妙数?
追问为什么相邻交换的最少次数正好等于逆序对数?
追问数字串里有重复数字时,怎么保证配对是最优的?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
旋转盒子
LeetCode 1861 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题