分类：Math
考察知识点：Math
最优解时间复杂度：O(n)
最优解空间复杂度：O(n)
60. Permutation Sequence
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:
"123""132""213""231""312""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"
代码：
100%Beat方法:
class Solution:
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
#边界条件
if n==0:
return ""
#存储nums
nums=[i+1 for i in range(n)]
#存储阶乘
facts=[1]
for i in range(1,n):
fact=facts[i-1]*i
facts.append(fact)
#为了从0开始 0~k-1
k=k-1
res=""
for i in range(n-1,-1,-1):
index=k//facts[i]
k=k%facts[i]
res+=str(nums[index])
nums.pop(index)
return res
讨论：
1.感觉这个解法稍微有些漏洞，比如k=25，而n=3的时候，index肯定是超了的，我觉得那个fact里还需要加一个，用来轮空
2.这道题主要还是用来理解数学，理解Permutation Sequence。
100%Beat！赛高！
