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(n²)。
  • 阶乘预处理：O(n)。
  • 逐位构造：共 n 次循环，每次 nums.remove(index) 是 O(n) 操作（数组拷贝）。
• 空间复杂度：O(n)。
  • 阶乘数组和可用列表均占用 O(n) 空间。

该方法通过阶乘分组和贪心构造，将时间复杂度从 O(n!) 降至 O(n²)，高效解决了大 n 场景下的排列定位问题，是处理“有序排列定位”类问题的经典思路。