首页 > 代码库 > LinkCode 第k个排列

LinkCode 第k个排列

# 递归的方法,创建一个visit判断此值是否已经添加过,每一层不断地循环,加入没有被访问的元素,直到最后结果的长度满足要求加入答案中
class Solution:
    """
    @param n: n
    @param k: the k-th permutation
    @return: a string, the k-th permutation
    """

    def getPermutation(self, n, k):
        nums = [x for x in range(1, n + 1)]
        visit = [0 for i in range(n)]
        self.ret = []
        self._permute(nums, visit, 0, [])
        # 因为结果要返回字符串类型,所以对数字类型进行处理
        ans = [str(j) for j in self.ret[k-1]]
        return "".join(ans)

    def _permute(self, nums, visit, count, ret):
        if count == len(nums):
            self.ret.append(ret)
            return
        for i in range(len(nums)):
            if visit[i] == 0:
                # ret += [nums[i]]  容易出错,如果加入这句后面需要还原,不然影响后面的循环
                visit[i] = 1
                self._permute(nums, visit, count + 1, ret + [nums[i]])
                visit[i] = 0

LinkCode 第k个排列