给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

range(1, n+1)的列表，以任意一个为起点的排列数为（n-1)!，所以先看起点是第几个数字，然后更新K，从原始列表中删除起点数字，迭代计算

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        factory = [1]
        nums = ['1']
        for i in range(1, n):
            factory.append(factory[i-1]*i)
            nums.append(str(i+1))
        k -= 1
        res = []
        for i in range(n-1, -1, -1):
            idx = k // factory[i]
            k = k % factory[i]
            
            res.append(nums[idx])
            del nums[idx]
        return ''.join(res)