60. 第k个排列
题目起源：力扣（LeetCode）
https://leetcode-cn.com/problems/permutation-sequence
题目
给出汇合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小程序列出所有排列状况，并一一标记，当 n = 3 时, 所有排列如下：
- "123"
- "132"
- "213"
- "231"
- "312"
- "321"
给定 n 和 k，返回第 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 开始抉择，逐步增大。当首元素确定之后，第二个元素同样是从小到大抉择的，例如 123，132 。
依据下面的剖析，咱们能够发现，假如给定 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, [])欢送关注
公众号 【书所集录】