[Leetcode][python]Permutation Sequence/第k个排列

迈不过友情╰ 2022-06-07 05:47 157阅读 0赞

## 题目大意 ##

找出由\[1,2,3…n\]中所有数字组成的序列中第k大的。

注意点：  
n为1-9中某一个数字

## 解题思路 ##

来自：[http://www.cnblogs.com/zuoyuan/p/3785530.html][http_www.cnblogs.com_zuoyuan_p_3785530.html]  
我采用的方法是计算第k个Permutation。  
假设n = 6，k = 400  
先计算第一位，  
第一位为6，那么它最少也是第5! \* 5 + 1个排列，这是因为第一位为1/2/3/4/5时，都有5!个排列，因此第一位为6时，至少是第5! \* 5 + 1个排列（这个排列为612345）。  
5! \* 5 + 1 = 601 > k，所以第一位不可能是6.  
一个一个地枚举，直到第一位为4时才行，这时，4xxxxx至少为第5! \* 3 + 1 = 361个排列。  
然后计算第二位，  
与计算第一位时的区别在于，46xxxx至少为第4! \* 4 + 1 = 97个排列，这是因为比6小的只有5/3/2/1了。  
最后可以计算出第二位为2。

## 代码 ##

### 回溯（自己的思路） ###

这题标准回溯结构，所以我也尽量标准写法

class Solution(object):
        def getPermutation(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: str
            """
            curr = []
            self.result = ''
            for i in range(1, n+1):
                curr.append(i) 
            self.getPermutationHelper(n, k, curr)
            return self.result
        def getPermutationHelper(self, index, rest, curr):
            # print index, rest, '结果str：', curr
            if index == 0:
                return 
            for i in range(index-1, -1, -1):
                temp = math.factorial(index-1)
                # print temp, i, rest - (temp * i + 1)
                if rest - (temp * i + 1) >= 0:
                    self.result += str(curr[i])
                    curr.pop(i)
                    # print(curr)
                    self.getPermutationHelper(index-1, rest - (temp * i), curr)
                    break

### 网上解法 ###

其实思路是一样的，我的效率低下。

class Solution:
    
        def getPermutation(self, n, k):
            res = ''
            k -= 1
            fac = 1
            for i in range(1, n): fac *= i
            num = [1, 2, 3, 4, 5, 6, 7, 8, 9]
            for i in reversed(range(n)):
                curr = num[k/fac]
                res += str(curr)
                num.remove(curr)
                if i !=0:
                    k %= fac
                    fac /= i
            return res

## 总结 ##

回溯是有基本结构的

[http_www.cnblogs.com_zuoyuan_p_3785530.html]: http://www.cnblogs.com/zuoyuan/p/3785530.html