乐趣区

关于leetcode:LeetCode-60-第k个排列-Python

60. 第 k 个排列


题目起源:力扣(LeetCode)
https://leetcode-cn.com/problems/permutation-sequence

题目


给出汇合 [1,2,3,…,n],其所有元素共有 n! 种排列。

按大小程序列出所有排列状况,并一一标记,当 n = 3 时, 所有排列如下:

  • “123”
  • “132”
  • “213”
  • “231”
  • “312”
  • “321”

给定 nk,返回第 k 个排列。

阐明:

  • 给定 n 的范畴是 [1, 9]。
  • 给定 k 的范畴是 [1, n!]。

示例 1:

 输出: n = 3, k = 3
输入: "213"

示例 2:

 输出: n = 4, k = 9
输入: "2314"

解题思路


思路:DFS + 剪枝

先审题,题目中阐明,给定汇合 [1, 2, 3, ..., n]n! 中排列。按大小程序列出所有排列状况,进行标记,而后返回第 k 个排列。

那么依照题意,咱们最容易想到的就是列出 [1, 2, 3 ..., n] 个元素全排列,而后返回第 k 个排列,然而这样效率可能会非常低,而且咱们也没有必要去求得所有的全排列。

在这里咱们能够先看看法则,题目中开始就说了,依照大小程序列出所有排列状况。也就说,n 个元素组合的数,这个数每个元素都是从小到大进行抉择的。例如示例 1:

 输出:n = 3, k = 3

在这里,给定的 n 为 3,那么要组合的数为 3 位数。这里它的全排列状况如下:

  • “123”
  • “132”
  • “213”
  • “231”
  • “312”
  • “321”

咱们能够发现,第一个元素是从 1 开始抉择,逐步增大。当首元素确定之后,第二个元素同样是从小到大抉择的,例如 123132

依据下面的剖析,咱们能够发现,假如给定 n 个元素,

当确定首元素时,前面元素则有 (n-1)! 中排列组合数,也就意味着首元素抉择后,以后分支会产生 (n-1)! 种排列数。以此类推,当确定后面两个元素时,前面能产生的排列数则为 (n-2)!。那么:

  • 当 k 大于后面分支可能产生的排列数时,咱们能够间接跳过;
  • 当 k 小于或等于以后分支产生的排列数时,也就阐明要找的答案在这个分支的某个排列中,这个时候,咱们递归去求解(确定一一元素)。

具体的代码如下。

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        # 阶乘数组
        arr = [1 for _ in range(n+1)]
        for i in range(2, n+1):
            arr[i] = arr[i-1] * i

        used = [False for _ in range(n+1)]


        def dfs(k, tmp):
            """
            Args:
                tmp: 排列元素抉择数组
            """
            cnt = len(tmp)

            if cnt == n:
                return ''.join(tmp)
            
            # 排列数,# 这里留神,刚开始排列数组中元素个数 cnt 为 0,# 此时要开始增加元素,所以要去除以后元素,计算后续的排列数,# 所以排列数为 (n-cnt-1)!,对应 arr[n-cnt-1]
            arr_num = arr[n-cnt-1]
            
            # 比拟 k 与以后分支的排列数
            for i in range(1, n+1):
                if used[i]:
                    continue
                if k > arr_num:
                    # 剪枝
                    # 如果 k 大于以后分支排列数,更新 k,跳过以后分支
                    k -= arr_num
                    continue
                # 否则,将以后数增加到排列中
                tmp.append(str(i))
                used[i] = True
                # 持续向下抉择
                return dfs(k, tmp)

        
        return dfs(k, [])

欢送关注


公众号【书所集录】

退出移动版