leetcodeday60 –排列序列

给出集合 [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 <= n <= 9
• 1 <= k <= n!

# @lc app=leetcode.cn id=60 lang=python3
#
# [60] 排列序列
#

# @lc code=start
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        nums=[i for i in range(1,n+1)]

        def subgetPermutation(N,k,nums,str1): 
          import math
            #print(k)
          while 1:
            if k<0 or len(nums)==1: 
                str1=str1+str(nums[0])
                return str1
            x=math.factorial(N-1)
            for i in range(1,len(nums)+1):
                if i*x>=k:    
                    k=k-(i-1)*x if k-(i-1)*x>0 else k
                    N=N-1
                    #print(i,k,N,nums)

                    str1=str1+str(nums[i-1])
                    #print(str1)
                    nums.remove(nums[i-1])
                    #print(nums)
                    break
        return subgetPermutation(n,k,nums,"")
# @lc code=end