排列序列

笨办法是真把排列一个个列出来数到第 9 个。n 一大(比如 n=9 有 36 万个),数到 k 会慢到爆,我们要更聪明的办法。

n=4 时,第一位是 1 的排列有 3!=6 个、第一位是 2 的也有 6 个……排列被切成每块 6 个的整齐区块。这就是不用一个个数的突破口。

排列分块图 · 每块 (n−1)! = 6 个：把 24 个排列按首位分成 4 块、每块 6 个。k=9 落在「首位为 2」这一块里——所以答案第一位必是 2。我们用除法直接算出在第几块。

把 k 减 1 变成从 0 数起的下标,除以块大小得到「取第几个数」,取余得到「在块内的新排名」。下面用 n=4,k=9 一位一位演给你看。

候选池就绪 · [1,2,3,4]：这排格子是候选数字池 [1,2,3,4],谁被取走就变灰。先把 k 减 1 变成 8(从 0 数起)。准备定第 1 位。

第 1 位 · 算块大小 3! = 6：定第 1 位时,后面还剩 3 个数自由排,每块有 3! = 6 个排列。拿 8 去除以 6,看落在第几块。

第 1 位 · idx = 8 / 6 = 1：8 ÷ 6 = 1(整除),所以取候选池下标 1 的数,也就是 2。紫框指着它——第 1 位定为 2。

第 1 位 · 取走 2,拼进答案：把 2 取走拼进答案,这格变灰封存(不再参与)。候选池实际只剩 [1,3,4]。答案现在是 "2"。

第 1 位 · 更新 k = 8 % 6 = 2：8 ÷ 6 余 2,把 k 更新成 2——意思是「在首位为 2 的这 6 个排列里,我要第 2 个(从 0 起)」。继续定第 2 位。

第 2 位 · 算块大小 2! = 2：定第 2 位时,候选池(灰掉 2 后)剩 1、3、4 共 3 个,每块 2! = 2 个排列。拿 k=2 去除以 2。

第 2 位 · idx = 2 / 2 = 1：2 ÷ 2 = 1,取剩余候选 [1,3,4] 里下标 1 的数。1 是第 0 个、3 是第 1 个——所以第 2 位是 3。注意是在没被灰掉的数里数。

第 2 位 · 取走 3,拼进答案：取走 3 拼进答案,这格也变灰。候选池剩 [1,4]。答案变 "23"。

第 2 位 · 更新 k = 2 % 2 = 0：2 ÷ 2 余 0,k 归 0。k=0 是个友好信号:剩下每一位都直接取候选池里最小的那个。继续第 3 位。

第 3 位 · 块大小 1! = 1：剩 1、4 两个,块大小 1!=1。idx = 0÷1 = 0,取剩余候选里下标 0 的数,也就是最小的 1。

第 3 位 · 取走 1,拼进答案：取走 1 拼进答案,变灰。k 仍是 0。候选池只剩 [4] 一个数了。答案 "231"。

第 4 位 · 只剩一个 → 4：最后一位,候选池只剩 4,直接拿走。紫框指着它——第 4 位是 4。

完成 · 答案 = "2314"：四位全部定完。按取走顺序拼起来:2、3、1、4 → 答案 "2314"。全程没数过一个排列,直接用阶乘除法跳到位。

再演一例 · n=3, k=3：换 n=3, k=3 再走一遍(灰掉 4,只用前 3 个)。k 减 1 得 2。看公式是不是照样把答案算出来。

n=3 · 第 1 位 idx = 2 / 2! = 1：剩 3 个数、块大小 2!=2。2÷2 = 1,紫框指向下标 1 的 2。第 1 位定为 2。

n=3 · 取走 2 + 更新 k：取走 2 拼进答案、变灰。k 更新 2%2 = 0,接下来每位取剩余最小的。

n=3 · 第 2 位取剩余最小 → 1：k 是 0,第 2 位直接取剩余候选里最小的 1。答案变 "21"。

n=3 · 第 3 位 → 3,完成：最后只剩 3,拿走。答案 "213"——和手数 [123,132,213] 第 3 个完全吻合,公式照样灵。

魔法在于:排列天然按首位分块、块大小是阶乘。除法跳到块、取余进块内,把「数到第 k 个」变成 n 次算术。

雷区实演 · 忘了 k 先减 1：若不先把 k 减 1,首位 idx 这次碰巧也得 1,但取余会得 3(应为 2)→ 后面每一位都偏,排出错误答案。k 减 1 是地基。

边界三连：最小 k=1(全升序)、最大 k=n!(全降序)、单元素 n=1,三种边界过了就稳。

面试追问：把「阶乘分块 + 除法定位」和「k 减 1 的原因」讲清,是这题的得分点。