【题目】

给出集合 [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!

【题目解析】

解题方法

1. 初始化：从1到n的数字列表，用于构建排列；一个记录阶乘的数组，用于快速计算不同长度下的排列数。

2. 寻找第k个排列：

   • 对于n个数，第一个数字的位置可以通过(k-1)/(n-1)!确定，其中(n-1)!表示除第一个数字外，剩下的数字组成的排列总数。
   • 确定第一个数字后，从列表中移除该数字，更新k值为k % (n-1)!，继续确定下一个数字。
   • 重复上述过程直到所有数字确定。

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)，需要额外空间存储阶乘数值和当前可选数字列表。

实践意义

这种算法为解决大规模排列问题提供了有效的工具，尤其是在需要高效处理大量数据、直接找到解而不是枚举所有可能的情况时。在数据科学、密码学等领域，找到快速解决组合数学问题的方法具有重要的应用价值。此外，学习和实现这种算法可以帮助提升对组合数学和算法设计的理解，增强解决复杂问题的能力。

题目链接

排列序列