LeetCode 60: Permutation Sequence (Factorial Number System Unranking)
LeetCode 60MathCombinatoricsToday we solve LeetCode 60 - Permutation Sequence.
Source: https://leetcode.com/problems/permutation-sequence/
English
Problem Summary
Given n and k, list all permutations of numbers 1..n in lexicographic order, and return the k-th permutation string.
Key Insight
For fixed first digit, permutations split into equal-sized blocks of (n-1)!. So the k-th permutation can be built digit by digit using factorial buckets (a classic unranking process).
Brute Force and Limitations
Generating all permutations and sorting is O(n! · n), which is wasteful. We only need one permutation, so direct bucket selection is much better.
Optimal Algorithm Steps (Factorial Unranking)
1) Build a list nums = [1..n] and factorial table.
2) Convert to zero-based index: k--.
3) For remaining length m, each leading choice controls a block of size (m-1)!.
4) Pick index idx = k / block, append nums[idx], remove it.
5) Update k = k % block and continue until empty.
Complexity Analysis
Time: O(n²) (due to list removals).
Space: O(n).
Common Pitfalls
- Forgetting k-- (1-indexed to 0-indexed conversion).
- Wrong block size when remaining length changes.
- Removing wrong index from candidate list.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String getPermutation(int n, int k) {
int[] fact = new int[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) nums.add(i);
k--; // 1-indexed -> 0-indexed
StringBuilder sb = new StringBuilder();
for (int m = n; m >= 1; m--) {
int block = fact[m - 1];
int idx = k / block;
sb.append(nums.get(idx));
nums.remove(idx);
k %= block;
}
return sb.toString();
}
}import "strconv"
func getPermutation(n int, k int) string {
fact := make([]int, n+1)
fact[0] = 1
for i := 1; i <= n; i++ {
fact[i] = fact[i-1] * i
}
nums := make([]int, n)
for i := 0; i < n; i++ {
nums[i] = i + 1
}
k--
ans := ""
for m := n; m >= 1; m-- {
block := fact[m-1]
idx := k / block
ans += strconv.Itoa(nums[idx])
nums = append(nums[:idx], nums[idx+1:]...)
k %= block
}
return ans
}class Solution {
public:
string getPermutation(int n, int k) {
vector<int> fact(n + 1, 1);
for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
vector<int> nums;
for (int i = 1; i <= n; ++i) nums.push_back(i);
--k;
string ans;
for (int m = n; m >= 1; --m) {
int block = fact[m - 1];
int idx = k / block;
ans += to_string(nums[idx]);
nums.erase(nums.begin() + idx);
k %= block;
}
return ans;
}
};class Solution:
def getPermutation(self, n: int, k: int) -> str:
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i
nums = list(range(1, n + 1))
k -= 1
out = []
for m in range(n, 0, -1):
block = fact[m - 1]
idx = k // block
out.append(str(nums[idx]))
nums.pop(idx)
k %= block
return "".join(out)/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getPermutation = function(n, k) {
const fact = Array(n + 1).fill(1);
for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
const nums = [];
for (let i = 1; i <= n; i++) nums.push(i);
k -= 1;
let ans = "";
for (let m = n; m >= 1; m--) {
const block = fact[m - 1];
const idx = Math.floor(k / block);
ans += String(nums[idx]);
nums.splice(idx, 1);
k %= block;
}
return ans;
};中文
题目概述
给定 n 和 k，把 1..n 的全排列按字典序排列，返回第 k 个排列字符串。
核心思路
固定首位后，每个首位对应的排列数量都是 (n-1)!。因此可以按“阶乘分桶”逐位确定答案，不需要生成全部排列。
基线解法与不足
暴力生成所有排列再取第 k 个，复杂度接近 O(n! · n)，在本题中完全没必要。
最优算法步骤（阶乘进制反排名）
1）准备候选数字列表 [1..n] 和阶乘表。
2）将 k 转为 0 下标：k--。
3）剩余位数为 m 时，每个前缀块大小为 (m-1)!。
4）取 idx = k / block 作为当前位，加入答案并从候选列表删除。
5）更新 k = k % block，继续下一位。
复杂度分析
时间复杂度：O(n²)（主要来自数组/列表删除）。
空间复杂度：O(n)。
常见陷阱
- 忘记把 k 从 1 下标转成 0 下标。
- 每一轮 block 计算错误。
- 删除候选数字时索引错位。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String getPermutation(int n, int k) {
int[] fact = new int[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) nums.add(i);
k--; // 1-indexed -> 0-indexed
StringBuilder sb = new StringBuilder();
for (int m = n; m >= 1; m--) {
int block = fact[m - 1];
int idx = k / block;
sb.append(nums.get(idx));
nums.remove(idx);
k %= block;
}
return sb.toString();
}
}import "strconv"
func getPermutation(n int, k int) string {
fact := make([]int, n+1)
fact[0] = 1
for i := 1; i <= n; i++ {
fact[i] = fact[i-1] * i
}
nums := make([]int, n)
for i := 0; i < n; i++ {
nums[i] = i + 1
}
k--
ans := ""
for m := n; m >= 1; m-- {
block := fact[m-1]
idx := k / block
ans += strconv.Itoa(nums[idx])
nums = append(nums[:idx], nums[idx+1:]...)
k %= block
}
return ans
}class Solution {
public:
string getPermutation(int n, int k) {
vector<int> fact(n + 1, 1);
for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
vector<int> nums;
for (int i = 1; i <= n; ++i) nums.push_back(i);
--k;
string ans;
for (int m = n; m >= 1; --m) {
int block = fact[m - 1];
int idx = k / block;
ans += to_string(nums[idx]);
nums.erase(nums.begin() + idx);
k %= block;
}
return ans;
}
};class Solution:
def getPermutation(self, n: int, k: int) -> str:
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i
nums = list(range(1, n + 1))
k -= 1
out = []
for m in range(n, 0, -1):
block = fact[m - 1]
idx = k // block
out.append(str(nums[idx]))
nums.pop(idx)
k %= block
return "".join(out)/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getPermutation = function(n, k) {
const fact = Array(n + 1).fill(1);
for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
const nums = [];
for (let i = 1; i <= n; i++) nums.push(i);
k -= 1;
let ans = "";
for (let m = n; m >= 1; m--) {
const block = fact[m - 1];
const idx = Math.floor(k / block);
ans += String(nums[idx]);
nums.splice(idx, 1);
k %= block;
}
return ans;
};
Comments