LeetCode 60：排列序列

問題定義與核心挑戰

給定整數 n 和 k，返回集合 {1,2,...,n} 的第 k 個字典序排列。直接生成所有排列再遍歷到第 k 個的方法（時間復雜度 O(n!)）會因 n≥10 時階乘爆炸而超時，因此需要 數學推導 + 貪心構造 的高效解法。

核心思路：階乘定位法

利用階乘的分組特性，逐位確定排列的每個數字：

1. 階乘分組：對于 n 個數字，每個首位固定后，剩余 n-1 個數字的排列數為 (n-1)!。例如，n=3 時，首位為 1 的排列有 2! = 2 種（123、132）。
2. 逐位推導：通過計算 k-1（轉換為 0-based 索引）與階乘的商和余數，確定當前位的數字，并更新 k 為余數+1（保持后續推導的 1-based 邏輯）。

算法步驟詳解

步驟 1：預處理階乘數組

計算 0! 到 (n-1)!，用于快速確定每組的排列數量：

// 階乘數組，fact[i] = i!
long[] fact = new long[n];
fact[0] = 1; // 0! = 1
for (int i = 1; i < n; i++) {fact[i] = fact[i-1] * i;
}

• 例如，n=4 時，fact = [1, 1, 2, 6]（對應 0!、1!、2!、3!）。

步驟 2：初始化可用數字列表

維護一個動態列表，存儲當前未使用的數字（初始為 1~n）：

List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {nums.add(i);
}

步驟 3：逐位構造排列

從高位到低位（共 n 位），依次確定每個位置的數字：

StringBuilder res = new StringBuilder();
k--; // 轉換為 0-based 索引（核心！否則無法對齊階乘分組）for (int i = 0; i < n; i++) {// 當前剩余數字的數量：n - i// 當前階乘：(n-1-i)! → 對應剩余數字的排列數long currentFact = fact[n-1 - i];// 計算當前位的數字索引：k / currentFactint index = (int) (k / currentFact);// 取出數字，加入結果res.append(nums.get(index));// 從可用列表中移除該數字nums.remove(index);// 更新 k 為余數（下一輪的 k 是余數）k %= currentFact;
}

關鍵邏輯解析

1. k-- 的必要性：
   題目中 k 是1-based（如示例 1 中 k=3 對應第 3 個排列），但階乘分組的索引是 0-based。通過 k-- 轉換為 0-based 索引，確保計算時與階乘分組對齊。

2. 階乘的作用：
   currentFact = (n-1-i)! 表示剩余 n-i 個數字時，每個首位對應的排列數。例如，當確定第 1 位（i=0）時，currentFact = (n-1)!，即每個首位對應 (n-1)! 種排列。

3. 索引計算與數字移除：

   • index = k / currentFact：確定當前位應選可用列表中的第 index 個數字（因為前 index 組的排列數已被跳過）。
   • nums.remove(index)：從可用列表中移除已選數字，避免重復使用。
   • k %= currentFact：更新 k 為當前組內的剩余索引，用于下一輪計算。

完整代碼（Java）

import java.util.ArrayList;
import java.util.List;class Solution {public String getPermutation(int n, int k) {// 1. 預處理階乘數組：fact[i] = i!long[] fact = new long[n];fact[0] = 1; // 0! = 1for (int i = 1; i < n; i++) {fact[i] = fact[i-1] * i;}// 2. 初始化可用數字列表：[1, 2, ..., n]List<Integer> nums = new ArrayList<>();for (int i = 1; i <= n; i++) {nums.add(i);}// 3. 逐位構造結果StringBuilder res = new StringBuilder();k--; // 轉換為 0-based 索引，方便計算for (int i = 0; i < n; i++) {// 當前剩余數字的排列數：(n-1-i)!long currentFact = fact[n-1 - i];// 計算當前位的數字索引int index = (int) (k / currentFact);// 取出數字，加入結果res.append(nums.get(index));// 移除已選數字nums.remove(index);// 更新 k 為余數k %= currentFact;}return res.toString();}
}

示例驗證（以示例 2 為例）

輸入：n=4, k=9
預期輸出："2314"

推導過程：

1. 階乘數組：fact = [1, 1, 2, 6]（對應 0!~3!）。
2. 初始化：nums = [1,2,3,4]，k=9→k-1=8（轉換為 0-based）。

步驟 i	剩余數字	currentFact	index = 8 / currentFact	選中數字	nums 變為	k = 8 % currentFact
0	[1,2,3,4]	6 (3!)	8 / 6 = 1	2	[1,3,4]	8 % 6 = 2
1	[1,3,4]	2 (2!)	2 / 2 = 1	3	[1,4]	2 % 2 = 0
2	[1,4]	1 (1!)	0 / 1 = 0	1	[4]	0 % 1 = 0
3	[4]	1 (0!)	0 / 1 = 0	4	[]	0 % 1 = 0

最終結果："2314"，與示例一致。

復雜度分析

• 時間復雜度：O(n2)。
  • 階乘預處理：O(n)。
  • 逐位構造：共 n 次循環，每次 nums.remove(index) 是 O(n) 操作（數組拷貝）。
• 空間復雜度：O(n)。
  • 階乘數組和可用列表均占用 O(n) 空間。

該方法通過階乘分組和貪心構造，將時間復雜度從 O(n!) 降至 O(n2)，高效解決了大 n 場景下的排列定位問題，是處理“有序排列定位”類問題的經典思路。