欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LeetCode】【60. Permutation Sequence】【python版】

程序员文章站 2022-07-14 14:38:10
...

Description:
The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

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

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

思路:题目已经说明是n个不同的数字会有n!中排列方式,根据下图对“1234”的全排列,我们也能很明显看出这个结果是怎么得到的。按照第一个字符可以分为4组,每组再按照第二个字符可以分为3组,每组再按照第三个字符可以分为2组,所以有4×3×2种排列方式。


【LeetCode】【60. Permutation Sequence】【python版】

假如我们想得到第9个排列,转换为数组下标也就是8,定位顺序为level 1(1) → level 2 (1) → level 3 (0),下面来分析一下定位如何确定:

  • 最高位可以取{1,2,3,4},并且每个数在最高位出现3! = 6次,那么第9个排列的最高位取值的下标为:8/6 = 1,也就是数字2
  • 次位可以取{1,3,4},并且每个数在次位出现2I = 2 次,那么第9个排列的次位取值下标为:(8%6)/2 = 1,也就是数字3
  • 第三位可以取{1,4},并且每个数在第三位出现1次,那么第9个排列的第三位取值下标为:(8%6%2)/1 = 0,也就是数字1
  • 最后一位只有一个选择数字4
  • 最终得到第9个排列位2314

ki表示在set中取值下标,n表示集合中数字个数,可以得到这样的推导式

k1=k/(n1)!
k=k%(n1)!

k2=k/(n2)!
k=k%(n2)!

kn1=k/1

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        import math
        numset = [i for i in range(1, n+1)]
        retnum = []
        k = k - 1
        while len(numset) > 1:
            n = n - 1
            index = k / math.factorial(n)
            retnum.append(str(numset[index]))
            k = k % math.factorial(n)
            numset.remove(numset[index])
        # 最后剩一个数字直接加在最后
        retnum.append(str(numset[0]))
        return ''.join(retnum)
相关标签: 面试 算法