排列序列
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时，所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
示例 1
示例 2
示例 3
模拟答题者思考
1. 最直接：用 #46「全排列」回溯生成全部 n! 个排列，排序后取第 k 个——n=9 时 9!≈36万 尚可，但思路笨重且浪费。
2. 重复在哪里？我们不需要列出所有排列，只需定位第 k 个——字典序排列有固定规律：以 1 开头的有 (n-1)! 个，以 2 开头的也有 (n-1)! 个，以此类推。
3. 关键转化：逐位确定——第 1 位选第 k // (n-1)! 小的可用数字；更新 k %= (n-1)! 后在剩余数字中重复，直到填完 n 位。
4. 手推 n=3, k=3：k 转 0-index 得 2；第 1 位块大小 2!=2，idx=2//2=1 选 2；k=0，剩余 [1,3] 依次填得 "213"。
5. 与 #31「下一个排列」对比：#31 给定排列求下一个，本题给定排名求排列——本质都是字典序与阶乘分解的互逆操作。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
fact | list<int> | 定义：阶乘表，fact[i] = i!，用于计算「固定前若干位后，剩余位有多少种排列」维护：预处理 fact[0]=1，递推 fact[i]=fact[i-1]*i，最大用到 fact[n-1]更新：只读；第 i 位（0-indexed）每个候选数字对应 fact[n-1-i] 种后续排列 |
k | int | 定义：目标排列在字典序中的排名（题面从 1 开始） 维护：进入循环前先 k -= 1 转为 0-indexed，便于整除取商更新：每确定一位数字后 k %= fact[n-1-i]，把问题缩小到该前缀下的第 k 个子排列 |
available | list<int> | 定义：尚未使用的数字集合，初始为 [1,2,...,n]维护：按字典序排列；每确定一位就从列表中删除已选数字 更新：第 i 位选 available[idx] 后 pop(idx)，保证后续只在剩余数字中选 |
idx | int | 定义：当前位应选 available 中第几个数字（0-indexed）维护： idx = k // fact[n-1-i]——每块大小为 fact[n-1-i]，商即块编号更新：每轮重新计算； n=3,k=3 时第一位 idx=1 选数字 2 |
ans | str | 定义：已确定前缀的排列字符串 维护：从左到右逐位追加 available[idx] 的字符更新：循环 n 次后 len(ans)==n，即为第 k 个排列 |
落码步骤
1. 预处理阶乘表 fact[0..n]，其中 fact[i]=i!
2. 初始化 available = [1,2,...,n]，ans = ""，令 k -= 1（转为 0-indexed）
3. 循环 i 从 0 到 n-1（逐位填第 i 个字符）
4. 计算块大小 block = fact[n - 1 - i]
5. idx = k // block，将 available[idx] 追加到 ans
6. 从 available 中删除已选数字，更新 k = k % block
7. 循环结束后返回 ans
代码实现
class Solution:
def getPermutation(self, n: int, k: int) -> str:
fact = [1] * (n + 1)
for i in range(2, n + 1):
fact[i] = fact[i - 1] * i
available = list(range(1, n + 1))
k -= 1 # 转为 0-indexed
ans = []
for i in range(n):
block = fact[n - 1 - i]
idx = k // block
ans.append(str(available[idx]))
available.pop(idx)
k %= block
return "".join(ans)class Solution {
public:
string getPermutation(int n, int k) {
vector<int> fact(n + 1, 1);
for (int i = 2; i <= n; i++) {
fact[i] = fact[i - 1] * i;
}
vector<int> available(n);
iota(available.begin(), available.end(), 1);
k--; // 转为 0-indexed
string ans;
for (int i = 0; i < n; i++) {
int block = fact[n - 1 - i];
int idx = k / block;
ans += to_string(available[idx]);
available.erase(available.begin() + idx);
k %= block;
}
return ans;
}
};
// 时间 O(n²)（erase 为 O(n)），空间 O(n)复杂度分析
O(n²)
O(n)
常见坑
忘记 k -= 1：题面 k 从 1 开始，不转换会导致第 1 个排列算成第 2 个，如 n=3,k=1 会错成 "132" 而非 "123"。
块大小用错下标：第 i 位（0-indexed）的块大小是 fact[n-1-i]，不是 fact[n-i] 或 fact[i]。
与 #46「全排列」混淆：#46 是枚举所有排列，本题是按排名直接构造一个排列，不需要回溯或 used 数组。
必测边界 Case
n = 3, k = 1 → "123"（字典序最小，k-1=0 每位 idx=0）
n = 3, k = 6 → "321"（3!=6，k-1=5 每位选最大可用数字）
n = 4, k = 9 → "2314"（验证阶乘分块：8//6=1 选 2，2//2=1 选 3）
n = 1, k = 1 → "1"（仅一种排列，循环一次即结束）
9! = 362880，fact[8] 在 int 范围内；O(n²) 共 81 次操作，远低于时限