0060：排列序列（★★）

力扣第 60 题

题目

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

相似问题：

• 0031：下一个排列
• 0046：全排列

分析

• 为了方便，令 k 减 1 使得从 0 开始
• 由排列组合知识可知：
  • 首位固定时有 (n-1)! 种情况
  • 第 k 个排列的首位即为第 k//(n-1)! 小的元素
  • 确定首位后，转为求剩下元素的第 k%(n-1)! 个排列
• 为了方便，维护一个有序数组 A，每次弹出确定的元素即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        res = ''
        A = list(range(1,n+1))
        k,s = k-1,factorial(n)
        for _ in range(n):
            s //= len(A)
            q,k = divmod(k,s)
            res += str(A.pop(q))
        return res

34 ms