第k个排列

https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1021/

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

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：

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

主要是找规律！现在要找第K个排列，假设N=4，K=8
我们从最高位往下找，第一位为1的，有321=6种可能，因为K=8，所以第1位必须为2才有可能，这样的话，剩下的数字134中，找出K=8-6的，即第二个排列就可以了。这样就有了循环的基础。
注意：

1. 循环中只用到N-1次，因为最后一个数字不用去排列了，这也保证了循环里面的除法不会为0
2. 从K得到的高位数，并不是直接等于他，而是只在数组中剩下的数字第K个排序。
3. 注意更新的逻辑不要出错，不仅要更新K，还要更新阶乘的值。
   代码如下：

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        if n == 1:
            return '1'
        m = 1
        arr = []
        # 计算n-1的阶乘
        for i in range(1,n):
            m *= i
            arr.append(str(i))
        arr.append(str(n))
        answer = ''
        start = n-1
        for i in range(0,n-1):
            # 获取首位大小，num是值在剩余数字中应该排名第几的，举例说明，如果123中，k=3，那首位应该是第二大的'2'，而'2'数组arr中对应的位置为1
            num = (k-1)/m 
            # k更新为选了首位后，剩下的排序，比如2选定后，相当于排除了以1为开头的数字
            k -= num*m
            # 更新下m的阶乘，m往下走一个
            m = m/start
            start -= 1
            # 这里注意是num是arr中第i大的数，比如2已经被选走了，那么下一轮就不能被选择了
            answer = answer + arr[num]
            del arr[num]
        answer += arr[0]
            
        return answer