京公网安备11010502063487号给定 n 和 k，返回 1 到 n 的所有排列按字典序排好后的第 k 个。最直接的做法是生成所有排列再取第 k 个，但排列个数是 n!，n = 9 时是 362880 个，只为了一个答案很浪费。更好的做法利用了排列的结构：以 1 开头的排列有 (n-1)! 个，以 2 开头的接着有 (n-1)! 个……所以用 k 除以 (n-1)! 就知道第一位是第几个数字，余数再决定后面的位，就像"阶乘进制"。本文用真实数据展示"k 忘了减 1"的错误有多致命，验证这个方法按字典序遍历了所有排列，实测它与枚举所有排列的耗时，给出五种语言的实现，并把逐位确定的过程做成分步演示。
完整题目见官方页面（链接在文末）。基准解是用 itertools.permutations 生成全部排列（按字典序），取第 k 个，与阶乘进制是完全不同的写法。一共 14 组用例，覆盖：官方示例、n = 1、k = 1（最小的排列）、k = n!（最大的排列）、n 取 9 的中间值：
输入 [3,3] 输出 "213" 输入 [4,9] 输出 "2314" 输入 [3,1] 输出 "123" 输入 [1,1] 输出 "1" 输入 [2,1] 输出 "12" 输入 [2,2] 输出 "21"
题目里 k 是"第几个"，从 1 开始数；而除法和余数的计算是从 0 开始的：前 (n-1)! 个排列（下标 0 到 (n-1)! - 1）都以最小的数字开头。所以要先把 k 减 1。下面是不减 1 的写法的真实结果，并统计了 n 从 1 到 7 的所有 (n, k) 组合：
# k 没有减 1 的写法 n=3, k=3: k 不减 1 -> 231 solve -> 213 n=4, k=9: k 不减 1 -> 2341 solve -> 2314 n=3, k=1: k 不减 1 -> 132 solve -> 123 n=3, k=6: k 不减 1 -> IndexError（下标越界） solve -> 321 n=4, k=24: k 不减 1 -> IndexError（下标越界） solve -> 4321 n 从 1 到 7、每个 k：共 5913 种，k 不减 1 的写法答错或越界 5913 种（100.0%）
不减 1 的写法，n = 3, k = 3 得到 231，而正确答案是 213；n = 3, k = 1 得到 132 而不是 123；k = n! 时更是直接下标越界。n 从 1 到 7 的全部 5913 种组合里，不减 1 的写法全部答错或越界（100%），没有一组碰巧对。这是一个整体偏移一位的错误，所以官方示例一跑就能发现，但是错误的答案看起来仍像合理的排列，容易被误认为是别的问题。
先算阶乘表，把 k 减 1。然后从高位到低位：还剩 i 位没定时，每个开头数字对应 (i-1)! 个排列，用 k 除以 (i-1)!，商是这一位选剩余数字（保持升序）里的第几个，取出来；余数作为新的 k，继续下一位。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；Java 用 List.remove(int) 取出，Go 用切片拼接，C++ 用 erase。
Python · 解法代码def solve(n, k): digits = list(range(1, n + 1)) # 还没用过的数字，始终保持升序 fact = [1] * (n + 1) for i in range(1, n + 1): fact[i] = fact[i - 1] * i # fact[i] = i! k -= 1 # 改成从 0 开始计数：第 k 个排列的下标是 k-1 res = [] for i in range(n, 0, -1): idx, k = divmod(k, fact[i - 1]) # 后面还剩 i-1 个位置，每个开头对应 (i-1)! 种排列：商就是这一位选第几个数字 res.append(str(digits.pop(idx))) return "".join(res)
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [3,3] → "213" [4,9] → "2314" [3,1] → "123" [1,1] → "1" [2,1] → "12" [2,2] → "21"
Java · 解法代码class Solution { public String getPermutation(int n, int k) { List<Integer> digits = new ArrayList<>(); // 还没用过的数字，始终保持升序 int[] fact = new int[n + 1]; fact[0] = 1; for (int i = 1; i <= n; i++) { digits.add(i); fact[i] = fact[i - 1] * i; // fact[i] = i! } k--; // 改成从 0 开始计数：第 k 个排列的下标是 k-1 StringBuilder sb = new StringBuilder(); for (int i = n; i >= 1; i--) { int idx = k / fact[i - 1]; // 后面还剩 i-1 个位置，每个开头对应 (i-1)! 种排列：商就是这一位选第几个数字 k %= fact[i - 1]; sb.append(digits.remove(idx)); } return sb.toString(); } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [3,3] → "213" [4,9] → "2314" [3,1] → "123" [1,1] → "1" [2,1] → "12" [2,2] → "21"
Go · 解法代码func getPermutation(n int, k int) string { digits := make([]int, n) // 还没用过的数字，始终保持升序 fact := make([]int, n+1) fact[0] = 1 for i := 1; i <= n; i++ { digits[i-1] = i fact[i] = fact[i-1] * i // fact[i] = i! } k-- // 改成从 0 开始计数：第 k 个排列的下标是 k-1 res := "" for i := n; i >= 1; i-- { idx := k / fact[i-1] // 后面还剩 i-1 个位置，每个开头对应 (i-1)! 种排列：商就是这一位选第几个数字 k %= fact[i-1] res += strconv.Itoa(digits[idx]) digits = append(digits[:idx], digits[idx+1:]...) } return res }
$ go build -o bin . && ./bin < cases.jsonl [3,3] → "213" [4,9] → "2314" [3,1] → "123" [1,1] → "1" [2,1] → "12" [2,2] → "21"
JavaScript · 解法代码function getPermutation(n, k) { const digits = []; // 还没用过的数字，始终保持升序 const fact = [1]; for (let i = 1; i <= n; i++) { digits.push(i); fact.push(fact[i - 1] * i); // fact[i] = i! } k--; // 改成从 0 开始计数：第 k 个排列的下标是 k-1 let res = ""; for (let i = n; i >= 1; i--) { const idx = Math.floor(k / fact[i - 1]); // 后面还剩 i-1 个位置，每个开头对应 (i-1)! 种排列：商就是这一位选第几个数字 k %= fact[i - 1]; res += digits.splice(idx, 1)[0]; } return res; }
$ node run.js < cases.jsonl [3,3] → "213" [4,9] → "2314" [3,1] → "123" [1,1] → "1" [2,1] → "12" [2,2] → "21"
C++ · 解法代码#include <string> #include <vector> using namespace std; class Solution { public: string getPermutation(int n, int k) { vector<int> digits; // 还没用过的数字，始终保持升序 vector<int> fact(n + 1, 1); for (int i = 1; i <= n; i++) { digits.push_back(i); fact[i] = fact[i - 1] * i; // fact[i] = i! } k--; // 改成从 0 开始计数：第 k 个排列的下标是 k-1 string res; for (int i = n; i >= 1; i--) { int idx = k / fact[i - 1]; // 后面还剩 i-1 个位置，每个开头对应 (i-1)! 种排列：商就是这一位选第几个数字 k %= fact[i - 1]; res += to_string(digits[idx]); digits.erase(digits.begin() + idx); } return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [3,3] → "213" [4,9] → "2314" [3,1] → "123" [1,1] → "1" [2,1] → "12" [2,2] → "21"
共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
把 n = 4 的全部 24 个 k 对应的排列列出来，检查是否严格递增，并且与 itertools.permutations 的顺序完全一致：
把 n = 4 的全部 24 个 k 对应的排列列出来，检查是否严格递增（字典序）、与 itertools 的顺序一致： 1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 严格递增且与 itertools.permutations 的顺序一致：True
k 从 1 到 24 对应的排列依次是 1234、1243、1324……4321，严格按字典序递增，与标准库生成的顺序完全一致。
k 取 n!（最后一个排列，这是枚举法要走到最后的情形），n 为 6 到 9，每个规模取三次中最快的一次：
n（k = n!，最后一个排列） | 暴力解 | 本文解法
6 | 0.037 ms | 0.001 ms
7 | 0.218 ms | 0.001 ms
8 | 2.218 ms | 0.002 ms
9 | 27.356 ms | 0.002 ms阶乘进制的耗时在 0.001 到 0.002 毫秒，几乎不随 n 变化，它只需要 O(n²)（每次从列表里取一个元素）；枚举全部排列的耗时随 n! 增长：n = 6 到 9 依次是 0.037ms、0.218ms、2.218ms、27.356ms，每增加 1 分别增长 5.9 倍、10.2 倍、12.3 倍。n 更大时枚举就不可行了，而阶乘进制本身只要求 k 不超过 n!。题目限制 n 不超过 9，Java 和 C++ 里用 int 存阶乘（9! = 362880）足够，n 更大就需要 64 位整数。
Python 版本另外和枚举所有排列的基准做了随机对拍，n 取 1 到 7，k 取 1 到 n! 的随机值：
随机对拍 20000 组（n 取 1 到 7，k 取 1 到 n! 的随机值），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 n = 4，k = 9。先把 k 换成从 0 开始的下标 8。第一位：每个开头对应 3! = 6 个排列，8 ÷ 6 = 1 余 2，选剩余数字 [1, 2, 3, 4] 里下标 1 的 2；第二位：每个开头对应 2! = 2 个，2 ÷ 2 = 1 余 0，选剩余 [1, 3, 4] 里下标 1 的 3；之后余数都是 0，依次选最小的 1 和 4。答案是 2314。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。