For permutations of n, the first (n-1)! permutations start with 1, next (n-1)! ones start with 2, ... and so on. And in each group of (n-1)! permutations, the first (n-2)! permutations start with the smallest remaining number, ...
take n = 3 as an example, the first 2 (that is, (3-1)! ) permutations start with 1, next 2 start with 2 and last 2 start with 3. For the first 2 permutations (123 and 132), the 1st one (1!) starts with 2, which is the smallest remaining number (2 and 3). So we can use a loop to check the region that the sequence number falls in and get the starting digit. Then we adjust the sequence number and continue.
每次确定该数字是处于按照当前第一个数字来划分的第几组，将对应位置的数字填入就行了
Because to get the k-th sequence, you only need to perform (k-1) transformation, as number is initialized as range(1, n+1) which is already the 1st term
O(nlogn)
class Solution:
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
import math
res = ""
nums = list(range(1, n + 1))
k -= 1
while n > 0:
n -= 1
lens = math.factorial(n)
i, k = k // lens, k % lens
res += str(nums[i])
nums.remove(nums[i])
return res