LeetCode刷题（python版）——Topic60排列序列

一、题设

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

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

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

给定 n 和 k，返回第 k 个排列。

示例 1：

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

示例 2：

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

示例 3：

输入：n = 3, k = 1
输出："123"

二、基本思路

1.法一：我直接无脑请参考：LeetCode刷题（python版）——Topic47全排列II，输出第k-1个下标转换成字符串即可，python过不了，但是java和js好像可以AC，不过效率很低。

2.法二：我称之为数学法：假设n = 4，k = 14：那么我们生成如下的序列：从下面的列出的可以轻松看出是在以3打头的组中，那么这个3是怎么来的呢，这个六个一组又有啥规律呢？答：我们知道在第一个数定了之后，那么他的剩余三个数的排列数即为（n-1）! 个，3可以看作是以(14 // 6)打头的第 (14 - 14 // 6) 个。可以参考一下法二找规律法的图解，十分清晰易懂。具体步骤如下：

        首先，定义一个 jc ：0!,1!,2!,3!,……,用于分组规则，used用来标记[1,n]的数是否已用过。

        那么当 n = 4 , k =14时：

        1.我们首先看是哪个大组的，那么先要用 k 减 3! ，直至剪了两次 3! 时发现 k = 2 < cut = 6,此时的 j = 3，也就正好的第三大组，也就是3打头，所以我们存入j。

以1打头：                        以2打头：                             以3打头：              以4打头：

[1,2,3,4]                           [2,1,3,4]                                 [3,1,2,4]                  [4,1,2,3]

[1,2,4,3]                           [2,1,4,3]                                 [3,1,2,4]                  [4,1,3,2]

[1,3,2,4]                           [2,3,1,4]                                 [3,1,2,4]                  [4,2,1,3]

[1,3,4,2]                           [2,3,4,1]                                 [3,1,2,4]                  [4,2,3,1]

[1,4,2,3]                           [2,4,1,3]                                 [3,1,2,4]                  [4,3,1,2]

[1,4,3,2]                           [2,4,3,1]                                 [3,1,2,4]                  [4,3,2,1]

    2.下一步我们抛开开头3：此时 k =2 ,这时我们需要进行看是哪个小分组了，那么此时分组的标准就是 2 ! ,故我们判断 k = 2 = cut = 2,也就是第一小组的最后一个而且 j 还没有存过，那么我们就不用减 2! 了 ，直接存入 j 即可。

以1打头：                        以2打头：                             以3打头：              以4打头：

[1,2,3,4]                           [2,1,3,4]                                 [3,1,2,4]                  [4,1,2,3]

[1,2,4,3]                           [2,1,4,3]                                 [3,1,4,2]                  [4,1,3,2]

[1,3,2,4]                           [2,3,1,4]                                 [3,2,1,4]                  [4,2,1,3]

[1,3,4,2]                           [2,3,4,1]                                 [3,2,4,1]                  [4,2,3,1]

[1,4,2,3]                           [2,4,1,3]                                 [3,4,1,2]                  [4,3,1,2]

[1,4,3,2]                           [2,4,3,1]                                 [3,4,2,1]                  [4,3,2,1]

三、代码实现

法一：Python超时

class Solution(object):
    def getPermutation(self, n, k):
        flag = [0 for i in range(n)]
        res = []
        def backtracking(nows,lis):# [],[1,2,3]
            if len(nows) == n:
                s = ""
                for i in range(n):
                    nows[i] = str(nows[i])
                s = "".join(nows)
                res.append(s)
                return
            for i in range(n):
                if flag[i] == 1:
                    continue
                if flag[i] == 0:
                    flag[i] = 1
                    nows.append(lis[i])
                    backtracking(nows,lis)
                    flag[i] = 0
                    nows.pop()      
 
        def init(n):
            lis = []
            for i in range(1, n+1):
                lis.append(i)
            return lis
        lis = init(n) # [1,2,3]
        backtracking([],lis)
        return res[k-1]

法二：AC

 def getPermutation(self, n, k):
        jc = [1,1,2,6,24,120,720,5040,40320,362880]
        # 可以看成以arr[i]为一组分为几组
        used = [False for _ in range(n+1)]# 看[1,2,3,4]哪个被用了就做标记，下次不能用了
        res = []
        for i in range(n-1,-1,-1):
            cut = jc[i] # 从大往小分组
            for j in range(1,n+1):
                if used[j]:
                    continue
                if k > cut:
                    k -= cut#被见了几次，余数就是组里的第几组
                    continue
                used[j] = True
                res.append(j)
                break
        return ''.join([str(i) for i in res])

四、效率总结

法一：

 

法二：