第 k 个排列如何用阶乘进制直接定位？（LeetCode 60）

简化版

1..n 的排列按字典序排列时，每个首位数字固定后都有 (n-1)! 个排列。因此可以把 k-1 看成 0 基排名：每次用 k / factorial 选当前位在剩余数字中的下标，再更新 k %= factorial。这就是阶乘进制思想。

详细版

String getPermutation(int n, int k) {
    List<Integer> nums = new ArrayList<>();
    int[] fact = new int[n + 1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i;
        nums.add(i);
    }
    k--; // 转成 0 基
    StringBuilder ans = new StringBuilder();
    for (int pos = n; pos >= 1; pos--) {
        int block = fact[pos - 1];
        int idx = k / block;
        ans.append(nums.remove(idx));
        k %= block;
    }
    return ans.toString();
}

如果用数组列表删除中间元素，删除是 O(n)，总时间 O(n^2)；若用平衡树或树状数组可优化选第 k 小。

完整版教学

一、为什么不能真的生成所有排列

排列总数是 n!，增长非常快：

9! = 362880
10! = 3628800

如果只要第 k 个，生成全部再排序太浪费。字典序排列有明显分块结构，可以直接跳块。

二、首位数字如何分块

对于 1..n，固定首位为某个数字后，剩下 n-1 个数字任意排列，共 (n-1)! 个。

首位	覆盖排名范围（1 基）
`1`	`1..(n-1)!`
`2`	`(n-1)!+1..2*(n-1)!`
`3`	`2(n-1)!+1..3(n-1)!`

所以第 k 个排列的首位可以用除法定位。

记忆钩子：排列序列不是回溯题，而是“按阶乘大小分块跳过”。

三、为什么先做 `k--`

数组下标是 0 基，而题目给的 k 通常是 1 基排名。把 k 减 1 后：

idx = k / block

就能直接得到剩余数字列表中的下标。否则边界如 k = block 时会选到下一块。

四、每一位怎么递推

选完当前位后，问题缩小为：在剩余数字里找某个子块内的第几个排列。

k = k % block
pos--

这和十进制拆位类似，只不过位权不是 10^i，而是阶乘 i!。

五、手推 n=4, k=9

先转 0 基：k = 8。

首位 block = 3! = 6，idx = 8 / 6 = 1，选 2，k = 2
第二位 block = 2! = 2，idx = 2 / 2 = 1，剩余 [1,3,4] 选 3，k = 0
第三位 block = 1! = 1，idx = 0，选 1
第四位选 4
答案 2314

每一步都在删除一个已选数字，剩余列表保持升序，保证字典序。

六、复杂度与优化

使用 ArrayList.remove(idx) 删除中间元素需要移动后续元素，单次 O(n)，总 O(n^2)。

如果 n 很大，可以用树状数组维护剩余数字，支持查询第 idx+1 个未删除数字，复杂度降到 O(n log n)。

七、常见误区与追问

误区：忘记 k--。 1 基排名直接除会在整块边界选错。
误区：每次都重新生成排列。 题目可用阶乘分块直接定位。
误区：选完数字后不从剩余列表删除。 排列不能重复使用数字。
追问：为什么每块大小是 (n-1)!？ 固定一位后剩余 n-1 个数字任意排列。
追问：复杂度是多少？ ArrayList 删除写法通常 O(n^2)。
追问：如何优化到 O(n log n)？ 用树状数组或有序集合查第 k 个剩余数字。

八、加强记忆

第 k 个排列的口诀是：k-- 转 0 基，按 (pos-1)! 分块，商选下标，余数进下一位。它是阶乘进制，不是暴力回溯；能手推 n=4,k=9，基本就不会忘。

简化版

详细版