【LeetCode】*0060 第k个排列

https://leetcode-cn.com/problems/permutation-sequence/

# -*- coding:utf-8 -*-

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        def back(i, flag_list, temp_list=[]):
            """
            回溯
            :return:
            """
            if i == n:
                output.append(temp_list)
                return
            for j in range(len(flag_list)):
                if flag_list[j] != 0:
                    flag_list[j] = 0
                    temp_list.append(j + 1)
                    back(i + 1, flag_list[:], temp_list[:])
                    flag_list[j] = 1
                    temp_list = temp_list[:-1]
        output = []
        flag_list = [1 for _ in range(n)]
        back(0, flag_list)
        res = ''
        for each in output[k-1]:
            res = res+str(each)
        return res
if __name__ == '__main__':
    n = 3
    k = 3
    print(Solution().getPermutation(n, k))

思路：回溯，和前面比较像。

但是这道题学到了一个新东西，康托展开，这东西也太强了，可以直接算出结果。

chs = [i for i in range(1, 10)]
        factor = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
        k -= 1
        ans = ''
        for i in range(n - 1, -1, -1):
            j, k = divmod(k, factor[i])
            ans += str(chs.pop(j))
        return ans