LeetCode刷题笔记：字节跳动-数组和排序(7)-第K个排列

7.第K个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1."123"
2."132"
3."213"
4."231"
5."312"
6."321"

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
给定 n 和 k，返回第 k 个排列。

示例一：

输入: n = 3, k = 3
输出: "213"

示例二：

输入: n = 4, k = 9
输出: "2314"

本题最开始的想法是找出当前数组的全排列并进行排序操作，然后返回其中的第K个排列，但是超出时间限制，代码如下：

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        num = []
        for i in xrange(1,n+1):
            num+=[i]
        res = [num[0]]
        a = num[1:]
        while a:
            x = a.pop(0)
            tmp = []
            while res:
                y = res.pop(0)
                if y ==1:
                    y=[1]
                for i in range(len(y)+1):
                    tmp.append(y[:i]+[x]+y[i:])
            res = tmp
        return ''.join(str(x) for x in sorted(res)[k-1])

之后发现，第K个排列与该数字的长度有关，假设当前有4个数字[1,2,3,4]，要求第7个排列.假设第一位固定，则后面3位全排列有6种排列方法，说明以数字1为开头的排列有6种，那第7个排列，肯定第一个数字是2，然后就是求首位数字是2的第1个排列；那么接着假设第1位和第2位固定为21，剩下的2位有2种排列方法，由于是第1个排列，所以继续进行假设，当循环到最后一位时，返回当前假设即可。代码如下：

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        if n==1:
            return '1'
        num = '123456789'
        num = num[:n]
        jcl = [0,1]
        res = []
        for i in range(2,n):
            jcl += [jcl[i-1]*i]
        while k:
            while jcl:
                tmp = jcl.pop()
                if tmp==0:
                    res.append(num[0])
                    k=0
                    break
                if k%tmp!=0:
                    res.append(num[k/tmp])
                    num = num[:k/tmp]+num[k/tmp+1:]
                    k = k%tmp
                if k%tmp==0:
                    res.append(num[k/tmp-1])
                    num = num[:k/tmp-1]+num[k/tmp:]
                    k=tmp
        return ''.join([str(x) for x in res])