Leetcode Permutation Sequence 第 k 個排列構造

Leetcode Permutation Sequence：直接構造第 k 個排列

題目： 給定 n 和 k，返回 1..n 的全排列中第 k 個（按字典序）。n ≤ 9。

數學構造法

• 固定第一位為 x，剩餘 n-1 位有 (n-1)! 種排列。
• 第 k 個排列的第一位是第 ceil(k / (n-1)!) 小的未用數字。
• 確定第一位後，問題縮減為在剩餘數字中找第 k' = k - (idx-1)*(n-1)! 個排列。
• 遞歸/迭代構造。

代碼實現細節

• 預計算階乘 fact[i] = i!。
• 將 k 減 1 變為 0-based 索引，便於整除取模：idx = k / fact[n-i-1]，k %= fact[n-i-1]。
• 用 vector nums 存可用數字，選取後 erase。

參考代碼

class Solution {
public:
    string getPermutation(int n, int k) {
        vector fact(n+1, 1);
        for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i;
        vector nums;
        for (int i = 1; i <= n; i++) nums.push_back(i);
        k--; // 0-based
        string res;
        for (int i = n; i >= 1; i--) {
            int idx = k / fact[i-1];
            res += char('0' + nums[idx]);
            nums.erase(nums.begin() + idx);
            k %= fact[i-1];
        }
        return res;
    }
};

複雜度

時間 O(n²)（erase 為 O(n)），空間 O(n)。n ≤ 9 瞬間通過。

關鍵技巧

• k-- 統一下標，避免處理整除邊界。
• 預計算階乘避免重複計算。
• 用 string 直接拼接結果。