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的，即第二个排列就可以了。这样就有了循环的基础。
注意：
- 循环中只用到N-1次，因为最后一个数字不用去排列了，这也保证了循环里面的除法不会为0
- 从K得到的高位数，并不是直接等于他，而是只在数组中剩下的数字第K个排序。
- 注意更新的逻辑不要出错，不仅要更新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
