【题目】
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
示例 1：
输入： n = 3, k = 3
输出： "213"
示例 2：
输入： n = 4, k = 9
输出： "2314"
示例 3：
输入： n = 3, k = 1
输出： "123"
提示：
1 <= n <= 91 <= k <= n!
【题目解析】
解题方法
初始化：从1到n的数字列表，用于构建排列；一个记录阶乘的数组，用于快速计算不同长度下的排列数。
-
寻找第k个排列：
- 对于n个数，第一个数字的位置可以通过
(k-1)/(n-1)!确定，其中(n-1)!表示除第一个数字外，剩下的数字组成的排列总数。 - 确定第一个数字后，从列表中移除该数字，更新
k值为k % (n-1)!，继续确定下一个数字。 - 重复上述过程直到所有数字确定。
- 对于n个数，第一个数字的位置可以通过
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# 阶乘数组，用于计算不同位置的索引
factorial = [1] * (n + 1)
for i in range(1, n + 1):
factorial[i] = factorial[i - 1] * I
# 因为k是从1开始计数的，我们将k转换为从0开始
k -= 1
# 初始化数字列表和结果字符串
nums = [str(i) for i in range(1, n + 1)]
result = ''
# 从最高位开始确定每个位置的数字
for i in range(n, 0, -1):
# 确定当前位置的数字
index = k // factorial[i - 1]
k %= factorial[i - 1]
# 将确定的数字加到结果字符串，并从列表中移除
result += nums.pop(index)
return result
执行效率
image.png
【总结】
适用问题类型
- 需要从排列组合中直接定位到特定位置的排列。
- 排列数量庞大，无法直接枚举所有排列的场景。
解决算法：基于阶乘数系统的直接计算法
这种算法通过将排列问题转换为阶乘数系统的问题来解决，利用数学原理直接计算出第k个排列的具体形态。
算法特点
- 高效率：直接根据给定的序号k计算出排列，避免了生成全部排列的巨大开销。
- 低空间消耗：除了最终的排列字符串，算法运行过程中仅需存储阶乘数值和当前可选数字，空间复杂度低。
- 易于实现：算法逻辑清晰，易于按照步骤实现。
时间复杂度与空间复杂度
-
时间复杂度：
O(n^2)，主要时间开销在于每次从列表中移除选定的数字，需要遍历列表。 -
空间复杂度：
O(n)，需要额外空间存储阶乘数值和当前可选数字列表。
实践意义
这种算法为解决大规模排列问题提供了有效的工具，尤其是在需要高效处理大量数据、直接找到解而不是枚举所有可能的情况时。在数据科学、密码学等领域，找到快速解决组合数学问题的方法具有重要的应用价值。此外，学习和实现这种算法可以帮助提升对组合数学和算法设计的理解，增强解决复杂问题的能力。
