60. 排列序列

🔴   🔖  递归 数学  🔗 力扣 LeetCode

题目

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Example 1:

Input: n = 3, k = 3

Output: "213"

Example 2:

Input: n = 4, k = 9

Output: "2314"

Example 3:

Input: n = 3, k = 1

Output: "123"

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

题目大意

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

示例 1：

输入： n = 3, k = 3

输出： "213"

示例 2：

输入： n = 4, k = 9

输出： "2314"

示例 3：

输入： n = 3, k = 1

输出： "123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

解题思路

这道题的核心是利用数学方法直接定位到第 k 个排列，而不是逐个生成所有排列。

1. 阶乘性质

对于长度为 n 的排列：

• 每个数字可以作为排列的第一个数字。
• 当第一个数字固定后，其余数字的排列共有 (n-1)! 种可能。

例如：

• 对于 n = 3 的排列 ["123", "132", "213", "231", "312", "321"]：
  • 第一个数字为 1 的排列有 2! = 2 个：["123", "132"]。
  • 第一个数字为 2 的排列有 2! = 2 个：["213", "231"]。
  • 第一个数字为 3 的排列有 2! = 2 个：["312", "321"]。

2. 如何确定第一个数字

• 使用 k 和 (n-1)! 的关系确定第一个数字。
• 计算 index = Math.floor((k-1) / (n-1)!)，这个 index 表示当前可用数字中哪个数字是第一个。
• 更新 k = k % (n-1)!，继续对剩余的排列进行同样的计算。

3. 重复以上过程

• 每次固定一个数字，直到所有数字固定为止。

---

算法步骤

1. 预计算阶乘：
   • 构造一个数组 factorial，保存 0! 到 (n-1)! 的值。
2. 维护候选数字：
   • 使用一个数组 nums 保存当前可用的数字（初始为 [1, 2, ..., n]）。
3. 逐位确定数字：
   • 对于第 i 位，计算 index 和更新 k。
   • 根据 index 从 nums 中取出数字，加入结果。

复杂度分析

• 时间复杂度：O(n^2)

  • 计算阶乘：O(n)。
  • 每次选取数字要进行数组的 splice 操作，复杂度为O(n)，最多取 n 次，总复杂度：O(n^2)。

• 空间复杂度：O(n)，存储阶乘和候选数字。

代码

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function (n, k) {
	// 计算阶乘
	const factorial = Array(n).fill(1);
	for (let i = 1; i < n; i++) {
		factorial[i] = factorial[i - 1] * i;
	}

	// 初始化候选数字
	const nums = Array.from({ length: n }, (_, i) => i + 1);
	let result = '';

	// 从最高位到最低位确定数字
	k--; // 转为从 0 开始的索引
	for (let i = n; i > 0; i--) {
		const index = Math.floor(k / factorial[i - 1]);
		result += nums[index];
		nums.splice(index, 1); // 移除已选数字
		k %= factorial[i - 1]; // 更新 k
	}

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
31	下一个排列	[✓]	数组 双指针	🟠	🀄️ 🔗
46	全排列	[✓]	数组 回溯	🟠	🀄️ 🔗