LeetCode Permutation Sequence：康托展開求第 k 個排列

問題描述

給定 n 和 k，返回集合 {1,2,...,n} 的所有排列中，按字典序排列的第 k 個排列（1-based）。例如 n=3, k=3 返回 "213"。

核心數學：康托展開與逆康托展開

康托展開（排列 → 序號）

對於排列 a₁a₂...aₙ，其序號（0-based）為：

X = a₁'·(n-1)! + a₂'·(n-2)! + ... + aₙ'·0!

其中 aᵢ' 是 aᵢ 之後**未使用**的數中比 aᵢ 小的個數。

逆康托展開（序號 → 排列） —— 本題核心

1. k-- 轉為 0-based。
2. 準備有序可用數字列表 nums = [1,2,...,n]。
3. 從高位到低位（i = n-1 ... 0）：
   • factorial = i!
   • index = k / factorial —— 當前位在可用列表中的索引。
   • 選取 nums[index] 加入結果，從列表中移除。
   • k %= factorial 更新剩餘序號。

完整代碼 (C++)

class Solution {
public:
    string getPermutation(int n, int k) {
        vector factorial(n, 1);
        for (int i = 1; i < n; ++i) factorial[i] = factorial[i-1] * i;

        vector nums;
        for (int i = 1; i <= n; ++i) nums.push_back('0' + i);

        k--; // 0-based
        string res;
        for (int i = n - 1; i >= 0; --i) {
            int idx = k / factorial[i];
            res.push_back(nums[idx]);
            nums.erase(nums.begin() + idx);
            k %= factorial[i];
        }
        return res;
    }
};

逐步演示：n=4, k=9 (求第 9 個)

1. k=8 (0-based)，nums=[1,2,3,4]，factorial=[1,1,2,6]
2. i=3 (3!=6)：idx=8/6=1 → 選 2，nums=[1,3,4]，k=8%6=2
3. i=2 (2!=2)：idx=2/2=1 → 選 3，nums=[1,4]，k=0
4. i=1 (1!=1)：idx=0/1=0 → 選 1，nums=[4]，k=0
5. i=0 (0!=1)：idx=0 → 選 4
6. 結果："2314" ✓

複雜度分析

• 時間：O(n²) — 主要是 vector::erase 為 O(n)。可用 Fenwick Tree/線段樹優化至 O(n log n)，但 n≤9 時 O(n²) 完全足夠。
• 空間：O(n) — 存儲階乘和可用數字列表。

關鍵點總結

• 0-based 轉換：k-- 是關鍵第一步。
• 階乘預計算：避免重複計算。
• 列表動態維護：已用數字必須移除，保證後續選擇正確。
• 邊界：k 不超過 n!（題目保證）。

總結

Permutation Sequence 是康托展開的教科書級應用。理解「階乘進制」下的索引選擇邏輯，不僅能解決此題，更能觸類旁通解決「字典序第 k 個組合/子集/排列」等組合數學問題。