难度: Hard
给出集合 [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!运行时间: 43 ms
内存: 15.9 MB
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# 计算阶乘数组
factorial = [1]
for i in range(1,n):
factorial.append(factorial[-1] * i)
# 初始化剩余数字列表
nums = [str(i) for i in range(1,n+1)]
# 初始化结果字符串
result = ""
# 确定每一位的数字
k -= 1
for i in range(n-1,-1,-1):
index = k // factorial[i]
result += nums.pop(index)
k -= index * factorial[i]
return result
这个题解使用了数学推导的方法，通过计算阶乘数组和确定每一位数字来生成第k个排列。具体步骤如下： 1. 计算阶乘数组 factorial，其中 factorial[i] 表示 i 的阶乘，用于后续计算每一位数字的索引。 2. 初始化剩余数字列表 nums，包含从 1 到 n 的所有数字。 3. 初始化结果字符串 result，用于存储最终的排列结果。 4. 从最高位开始，通过 k 除以 factorial[i] 的商确定每一位的数字，并将对应的数字从 nums 中移除，同时更新 k 的值。 5. 重复步骤4，直到确定了所有位的数字。 6. 返回生成的排列结果 result。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# 计算阶乘数组
factorial = [1]
for i in range(1,n):
factorial.append(factorial[-1] * i)
# 初始化剩余数字列表
nums = [str(i) for i in range(1,n+1)]
# 初始化结果字符串
result = ""
# 确定每一位的数字
k -= 1
for i in range(n-1,-1,-1):
# 计算当前位的数字索引
index = k // factorial[i]
# 将对应数字添加到结果字符串
result += nums.pop(index)
# 更新 k 的值
k -= index * factorial[i]
return result
在题解中，确定每一位数字的具体值的过程是通过计算 k 除以 factorial[i] 的商来获得当前位的索引。这里，factorial[i] 表示第 i+1 位数字后所有数字的排列组合数。索引用于从剩余数字列表 nums 中选择数字。例如，若索引为 2，则从 nums 中选择第三个数字。通过这种方法，可以根据 k 的值逐步确定每一位上的数字，直到构成完整的排列。
在计算每一位数字时，将 k 减去 'index * factorial[i]' 的目的是为了更新 k 的值，以便能正确计算下一位数字的索引。这个减法操作实际上是移除了当前确定的数字所代表的所有排列组合数量，因此更新后的 k 表示在剩余数字中，所需查找的新排列的相对位置。
将数字从剩余数字列表 nums 中移除是非常重要的操作，因为每选择一个数字作为排列的一部分后，这个数字就不应再被重复使用。此操作确保了每个数字在最终排列中只出现一次，遵循排列的定义（即每个数字唯一且仅用一次）。如果不移除已选数字，可能会导致重复使用相同的数字，进而生成错误的排列结果。
阶乘数组 factorial 的预处理主要是为了快速计算在任意位置上可能的排列数。每个 factorial[i] 存储的是从 i+1 到 n 的所有数字的排列数，即 (n-i)!。这样的预处理允许算法快速确定每个位置上的索引，从而有效地计算出每一步的数字选择。这种方法避免了重复计算阶乘，提高了整体算法的效率。