60. 排列序列
题目描述
数字 1 到 n 各用一次，可以组成 n! 个不同的排列。把每个排列写成一个字符串，再把这些字符串从小到大排序。
例如 n = 3 时，排好后依次为 "123"、"132"、"213"、"231"、"312"、"321"。
输入 n 和 k，返回排序后的第 k 个排列（k 从 1 开始计）。
示例 1
输入：n = 3, k = 3 输出："213"
解释：n = 3 时第 3 个排列是 "213"。
示例 2
输入：n = 4, k = 9 输出："2314"
示例 3
输入：n = 3, k = 1 输出："123"
解释：第 1 个排列就是最小的 "123"。
数据范围
1 <= n <= 91 <= k <= n!
解题思路
康托展开的逆运算。确定第一位后，后面 n-1 位共有 (n-1)! 种排法，所以按第一位可以把所有排列分成 n 组、每组 (n-1)! 个。先把 k 改为从 0 开始的编号，则 k // (n-1)! 就是第一位在剩余数字中的下标，k % (n-1)! 是在组内的编号，继续对后面的位重复。
为什么正确
每轮开始时，答案 = 已确定的前缀 + “剩余数字的第 k 个排列（从 0 开始编号）”。
复杂度分析
时间 O(n²)（从列表中删除元素每次 O(n)），空间 O(n)。
易错点
忘记把 k 减 1：k 是从 1 开始的编号，直接做除法会在 k 恰好是 (n-1)! 的倍数时选到下一组。另外不要用回溯枚举全部排列，n = 9 时会枚举 36 万种。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def getPermutation(self, n: int, k: int) -> str:
fact = [1] * n
for i in range(1, n):
fact[i] = fact[i - 1] * i
nums = [str(d) for d in range(1, n + 1)]
k -= 1
ans = []
for i in range(n - 1, -1, -1):
idx = k // fact[i]
k %= fact[i]
ans.append(nums.pop(idx))
return ''.join(ans)class Solution {
public String getPermutation(int n, int k) {
int[] fact = new int[n];
fact[0] = 1;
for (int i = 1; i < n; i++) {
fact[i] = fact[i - 1] * i;
}
List<Integer> nums = new ArrayList<>();
for (int d = 1; d <= n; d++) nums.add(d);
k -= 1;
StringBuilder ans = new StringBuilder();
for (int i = n - 1; i >= 0; i--) {
int idx = k / fact[i];
k %= fact[i];
ans.append(nums.remove(idx));
}
return ans.toString();
}
}class Solution {
public:
string getPermutation(int n, int k) {
vector<int> fact(n, 1);
for (int i = 1; i < n; i++) {
fact[i] = fact[i - 1] * i;
}
string nums;
for (int d = 1; d <= n; d++) nums += char('0' + d);
k -= 1;
string ans;
for (int i = n - 1; i >= 0; i--) {
int idx = k / fact[i];
k %= fact[i];
ans += nums[idx];
nums.erase(nums.begin() + idx);
}
return ans;
}
};func getPermutation(n int, k int) string {
fact := make([]int, n)
fact[0] = 1
for i := 1; i < n; i++ {
fact[i] = fact[i-1] * i
}
nums := []byte{}
for d := 1; d <= n; d++ {
nums = append(nums, byte('0'+d))
}
k -= 1
ans := []byte{}
for i := n - 1; i >= 0; i-- {
idx := k / fact[i]
k %= fact[i]
ans = append(ans, nums[idx])
nums = append(nums[:idx], nums[idx+1:]...)
}
return string(ans)
}var getPermutation = function(n, k) {
const fact = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
fact[i] = fact[i - 1] * i;
}
const nums = [];
for (let d = 1; d <= n; d++) nums.push(String(d));
k -= 1;
const ans = [];
for (let i = n - 1; i >= 0; i--) {
const idx = Math.floor(k / fact[i]);
k %= fact[i];
ans.push(nums.splice(idx, 1)[0]);
}
return ans.join('');
};function getPermutation(n: number, k: number): string {
const fact = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
fact[i] = fact[i - 1] * i;
}
const nums: string[] = [];
for (let d = 1; d <= n; d++) nums.push(String(d));
k -= 1;
const ans: string[] = [];
for (let i = n - 1; i >= 0; i--) {
const idx = Math.floor(k / fact[i]);
k %= fact[i];
ans.push(nums.splice(idx, 1)[0]);
}
return ans.join('');
}