【LeetCode】【60. Permutation Sequence】【python版】
程序员文章站
2022-07-14 14:38:10
...
Description:
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
1. “123”
2. “132”
3. “213”
4. “231”
5. “312”
6. “321”
Given n and k, return the kth permutation sequence.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
思路:题目已经说明是n个不同的数字会有n!中排列方式,根据下图对“1234”的全排列,我们也能很明显看出这个结果是怎么得到的。按照第一个字符可以分为4组,每组再按照第二个字符可以分为3组,每组再按照第三个字符可以分为2组,所以有4×3×2种排列方式。
假如我们想得到第9个排列,转换为数组下标也就是8,定位顺序为level 1(1) → level 2 (1) → level 3 (0),下面来分析一下定位如何确定:
- 最高位可以取{1,2,3,4},并且每个数在最高位出现3! = 6次,那么第9个排列的最高位取值的下标为:8/6 = 1,也就是数字2
- 次位可以取{1,3,4},并且每个数在次位出现2I = 2 次,那么第9个排列的次位取值下标为:(8%6)/2 = 1,也就是数字3
- 第三位可以取{1,4},并且每个数在第三位出现1次,那么第9个排列的第三位取值下标为:(8%6%2)/1 = 0,也就是数字1
- 最后一位只有一个选择数字4
- 最终得到第9个排列位2314
用表示在set中取值下标,n表示集合中数字个数,可以得到这样的推导式
…
class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
import math
numset = [i for i in range(1, n+1)]
retnum = []
k = k - 1
while len(numset) > 1:
n = n - 1
index = k / math.factorial(n)
retnum.append(str(numset[index]))
k = k % math.factorial(n)
numset.remove(numset[index])
# 最后剩一个数字直接加在最后
retnum.append(str(numset[0]))
return ''.join(retnum)