目录

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!

相似问题:

分析

  • 为了方便,令 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