60. Permutation Sequence（求全排列的第k个排列）

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 (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

如果用前面2道题的递归非递归都会超时。

只能用数学的方法计算。

 class Solution(object):

     def getPermutation(self, n, k):

         """

         :type nums: List[int]

         :rtype: List[List[int]]

         """

         k = k -1

         nums = list(range(1, n + 1))

         res = ''

         while len(nums)!=0:

             ai =int(k/self.fn(n-1))

             res += str(nums[ai])

             del nums[ai]

             k = k % self.fn(n-1)

             n = n - 1

         return res

     def fn(self, n):

         res = 1

         while n != 0:

             res = res * n

             n = n - 1

         return res

巴特西

60. Permutation Sequence（求全排列的第k个排列）

最新文章

热门文章