解题思路
factorial[i]保存有1到i的排列的总数，最后一项factorial[-i]就是1到n全排列的总数
如果是第factorial[-i]项，那肯定就是反序的1到n
否则，就通过不断确定第一项来确定排列
60. 排列序列
代码
class Solution:
def getPermutation(self, n: int, k: int) -> str:
elements = [str(i) for i in range(1, n+1)]
factorial = list(range(n+1))
for i in range(n+1):
if i > 1:
factorial[i] *= factorial[i-1]
return ''.join(permutation(elements, factorial, k))
def permutation(elements, factorial, k):
if len(elements) == 1: return elements
fact = factorial[len(elements)-1]
index = 0
while k > fact * (index+1):
index += 1
# fact*index < k < fact*(index+1)
first = elements[index] # 每一轮递归调用的index是非递增的
rest = elements[:index] + elements[index+1:]
return [first, *permutation(rest, factorial, k-fact*index)]
效果图
