0060. 排列序列
大约 3 分钟
---
0060. 排列序列
- 标签:递归、数学
- 难度:困难
题目链接
题目大意
描述:
给出集合 ,其所有元素共有 种排列。
按大小顺序列出所有排列情况,并一一标记,当 时, 所有排列如下:
"123"
"132"
"213"
"231"
"312"
"321"
给定 和 。
要求:
返回第 个排列。
说明:
- 。
- 。
示例:
- 示例 1:
输入:n = 3, k = 3
输出:"213"
- 示例 2:
输入:n = 4, k = 9
输出:"2314"
解题思路
思路 1:数学计算
核心思想:
通过数学计算直接确定第 个排列中每个位置上的数字,而不需要生成所有排列。
算法步骤:
- 初始化:创建候选数字列表 和结果字符串 。
- 计算阶乘:预计算 ,用于快速计算每个位置可能的排列数。
- 逐位确定:对于第 位(从 0 开始):
- 计算剩余 个数字的排列数:。
- 确定当前位应该选择第几个数字:。
- 将选中的数字添加到结果中,并从候选列表中移除。
- 更新 :。
- 返回结果:当所有位置都确定后,返回结果字符串。
关键点:
- 使用 是因为题目中的 从 开始,而数组索引从 开始。
- 每次确定一位后,需要从候选列表中移除已使用的数字。
- 通过数学计算避免了生成所有排列,大大提高了效率。
数学原理:
对于 个数字的排列,第 位确定后,剩余 个数字有 种排列方式。因此,第 位选择第 个候选数字时,会跳过 个排列。
思路 1:代码
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# 预计算阶乘数组
factorial = [1] * n
for i in range(1, n):
factorial[i] = factorial[i - 1] * i
# 创建候选数字列表
candidates = [str(i) for i in range(1, n + 1)]
result = []
k -= 1 # 转换为从 0 开始的索引
# 逐位确定每个位置的数字
for i in range(n):
# 计算当前位应该选择第几个候选数字
index = k // factorial[n - i - 1]
# 将选中的数字添加到结果中
result.append(candidates[index])
# 从候选列表中移除已使用的数字
candidates.pop(index)
# 更新k
k -= index * factorial[n - i - 1]
return ''.join(result)
思路 1:复杂度分析
- 时间复杂度:,其中 是数字的个数。需要遍历 次,每次需要 时间从候选列表中移除元素,因此总时间复杂度为 。
- 空间复杂度:,需要 空间存储阶乘数组、候选数字列表和结果列表。