• 分类：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:

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"

代码：

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！赛高！