python实现leetcode之60. 排列序列

解题思路

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)]