当前位置：首页 > ops >正文

LeetCode 60：排列序列

ops 2025/7/28 13:04:18

LeetCode 60：排列序列

在这里插入图片描述

问题定义与核心挑战

给定整数 n 和 k，返回集合 {1,2,...,n} 的第 k 个字典序排列。直接生成所有排列再遍历到第 k 个的方法（时间复杂度 O(n!)）会因 n≥10 时阶乘爆炸而超时，因此需要 数学推导 + 贪心构造 的高效解法。

核心思路：阶乘定位法

利用阶乘的分组特性，逐位确定排列的每个数字：

阶乘分组：对于 n 个数字，每个首位固定后，剩余 n-1 个数字的排列数为 (n-1)!。例如，n=3 时，首位为 1 的排列有 2! = 2 种（123、132）。
逐位推导：通过计算 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;
}

关键逻辑解析

k-- 的必要性：
题目中 k 是1-based（如示例 1 中 k=3 对应第 3 个排列），但阶乘分组的索引是 0-based。通过 k-- 转换为 0-based 索引，确保计算时与阶乘分组对齐。
阶乘的作用：
currentFact = (n-1-i)! 表示剩余 n-i 个数字时，每个首位对应的排列数。例如，当确定第 1 位（i=0）时，currentFact = (n-1)!，即每个首位对应 (n-1)! 种排列。
索引计算与数字移除：
- 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();}
}