解題說明
Permutation Sequence
題目描述：給定整數 n 和 k，回傳 1 到 n 所有數字按字典序排列的第 k 個排列字串。
解題思路：使用「階乘數系統（Factoradic Number System）」直接計算，無需枚舉所有排列。
核心觀察：n 個數字的所有排列中，固定第一個數字後，剩餘 (n-1)! 個排列。因此可以用 (k-1) / (n-1)! 決定第一個數字在剩餘數字列表中的索引，然後將 k 更新為 (k-1) % (n-1)! + 1，遞迴地對剩餘 n-1 個數字重複此過程，直到所有位置都填滿。
步驟：
- 將 k 調整為 0-indexed（
k -= 1）。 - 預先計算階乘陣列
fact[0..n]。 - 維護剩餘可用數字列表（初始為
[1, 2, ..., n]）。 - 對每個位置 i（從 n-1 到 0）：計算索引
idx = k / fact[i]，取出digits[idx]加入結果，從列表中移除該數字，更新k %= fact[i]。
C++ 解法
複雜度分析
時間複雜度：O(n²) — 外層迴圈執行 n 次，每次 digits.erase() 需要 O(n) 移動元素，總計 O(n²)。若改用鏈結串列或樹狀結構維護剩餘數字，可降至 O(n log n)。
空間複雜度：O(n) — 儲存階乘陣列與剩餘數字列表，結果字串亦為 O(n)。
虛擬碼
1. Compute factorial array: fact[0]=1, fact[i] = i * fact[i-1] for i in 1..n. 2. Initialize digits = [1, 2, ..., n]. 3. Set k = k - 1 (convert to 0-indexed). 4. Initialize result = "". 5. For i from n-1 down to 0: a. idx = k / fact[i] b. Append digits[idx] to result. c. Remove digits[idx] from digits. d. k = k % fact[i] 6. Return result.
其他解法
方法一：遞迴（分治）
以遞迴方式實作同樣的階乘數系統邏輯：solve(remaining_digits, k) 每次從剩餘數字中選出第 (k-1) / (len-1)! 個，再以 k % (len-1)! 遞迴。時間與空間複雜度相同，O(n²) 時間、O(n) 空間（遞迴棧），但程式碼較直觀。
方法二：逐一生成下一個排列（next_permutation）
從排列 [1,2,...,n] 開始，呼叫 C++ std::next_permutation 共 k-1 次，即可得到第 k 個排列。時間複雜度 O(k × n)，當 k 接近 n! 時極慢（不實用），但實作最簡單，適合理解排列的字典序概念。
延伸思考
- 如何反過來求解：給定一個 1 到 n 的排列字串，求它在字典序中排第幾位（即求其 Lehmer code / 階乘數）？
- 若數字範圍不是 1 到 n 而是任意給定的 n 個不重複整數，演算法需要如何調整？
- 若 n 很大（例如 n = 20），k 可能超過 int 範圍（20! ≈ 2.4 × 10¹⁸），應改用哪種資料型別，以及 C++ 中有哪些注意事項？