leetcode-60

发表于
字数统计: 1.3k字 | 阅读时长 ≈ 5分钟

60. 第k个排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

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

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。

代码及解析：

看到这种题，第一感觉直接暴力枚举，可能超时，但根据题目n<=9则不会超时，虽然不会超时，但这不是最明智的方法，此题可以利用康托逆运算。

康托展开

对于1-n的全排列，判断给定的序列的位置。

原理：

X=a[n]*(n-1)!+a[n-1]*(n-2)!+…+a[i]*(i-1)!+…+a[1]*0!
其中, a[i]为整数，并且0 <= a[i] <= i, 0 <= i < n, a[i]表示未出现元素中小于当前值的个数，X为小于该序列的个数，则x+1为该序列在所有排列中的位置，这就是康托展开。

例如有3个数（1，2，3），则其排列组合及其相应的康托展开值如下：

排列组合 名次 康托展开 值
123 1 0 2! + 0 1! + 0 * 0! 0
132 2 0 2! + 1 1! + 0 * 0! 1
213 3 1 2! + 0 1! + 0 * 0! 2
231 4 1 2! + 1 1! + 0 * 0! 3
312 5 2 2! + 0 1! + 0 * 0! 4
321 6 2 2! + 1 1! + 0 * 0! 5

比如其中的 231：

  • 想要计算排在它前面的排列组合数目（123，132，213），则可以转化为计算比首位小即小于2的所有排列「1 2！」，首位相等为2并且第二位小于3的所有排列「1 1！」，前两位相等为23并且第三位小于1的所有排列（0 0！）的和即可，康托展开为：1 2！+1 1+0 0=3。
  • 所以小于231的组合有3个，所以231的名次是4。

再举个例子说明。
在（1，2，3，4，5）5个数的排列组合中，计算 34152的康托展开值。

  • 首位是3，则小于3的数有两个，为1和2，a[5]=2，则首位小于3的所有排列组合为 a[5]*(5-1)!
  • 第二位是4，则小于4的数有两个，为1和2，注意这里3并不能算，因为3已经在第一位，所以其实计算的是在第二位之后小于4的个数。因此a[4]=2
  • 第三位是1，则在其之后小于1的数有0个，所以a[3]=0
  • 第四位是5，则在其之后小于5的数有1个，为2，所以a[2]=1
  • 最后一位就不用计算啦，因为在它之后已经没有数了，所以a[1]固定为0
  • 根据公式：
    X = 2 * 4! + 2 * 3! + 0 * 2! + 1 * 1! + 0 * 0! = 2 * 24 + 2 * 6 + 1 = 61
    所以比 34152 小的组合有61个，即34152是排第62。

逆康托展开：

对于上述例子，在（1，2，3，4，5）给出62可以算出起排列组合为 34152。由上述的计算过程可以容易的逆推回来，具体过程如下：

排第62名，则值为61即小于它的序列有61个。

  • 用 61 / 4! = 2余13，说明a[5]=2,说明比首位小的数有2个，所以首位为3。
  • 用 13 / 3! = 2余1，说明a[4]=2，说明在第二位之后小于第二位的数有2个，所以第二位为4。
  • 用 1 / 2! = 0余1，说明a[3]=0，说明在第三位之后没有小于第三位的数，所以第三位为1。
  • 用 1 / 1! = 1余0，说明a[2]=1，说明在第二位之后小于第四位的数有1个，所以第四位为5。
  • 最后一位自然就是剩下的数2啦。
  • 通过以上分析，所求排列组合为 34152

再比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
对于n=4, k=15 找到k=15排列的过程:
1 + 对2,3,4的全排列 (3!个)         
        2 + 对1,3,4的全排列 (3!个)         3, 1 + 对2,4的全排列(2!个)
        3 + 对1,2,4的全排列 (3!个)-------> 3, 2 + 对1,4的全排列(2!个)-------> 3, 2, 1 + 对4的全排列(1!个)-------> 3214
        4 + 对1,2,3的全排列 (3!个)         3, 4 + 对1,2的全排列(2!个)         3, 2, 4 + 对1的全排列(1!个)
        
        确定第一位:
            k = 14(从0开始计数)
            index = k / (n-1)! = 2, 说明第15个数的第一位是3 
            更新k
            k = k - index*(n-1)! = 2
        确定第二位:
            k = 2
            index = k / (n-2)! = 1, 说明第15个数的第二位是2
            更新k
            k = k - index*(n-2)! = 0
        确定第三位:
            k = 0
            index = k / (n-3)! = 0, 说明第15个数的第三位是1
            更新k
            k = k - index*(n-3)! = 0
        确定第四位:
            k = 0
            index = k / (n-4)! = 0, 说明第15个数的第四位是4
        最终确定n=4时第15个数为3214

所以此题根据康托逆展开代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        factorial=[]#存储阶乘
        order=[]#存储未出现的数
        factorial.append(1)
        temp=1
        res=[]
        for i in range(1,n+1):
            order.append(i)
            temp*=i
            factorial.append(temp)
        k-=1 #第k个，即小于它的有k-1个
        for i in range(n)[::-1]:
            index=k//factorial[i]
            res.append(order.pop(index))
            k-=factorial[i]*index
        return "".join([str(i) for i in res])
hey!baby,站住，点它!