60.-dikge-pai-lie.md

60. 第k个排列

https://leetcode-cn.com/problems/permutation-sequence/

解法一：

由于全排列按字典序，因此可以通过方法把所求序列计算出来。 例如求1~9的全排列的第360000个序列，从最高位开始，9！= 362880 = 8！* 9 > 359999，因此359999 // 8! = 8，可知另8个数全排列的话，359999可以将第9个数排完8种情况，而且数字不能重复取，这个数只有可能是9，将9取出，放在最高位。剩下的情况有359999 % 8! = 37439种，进入下一轮迭代。nums剩下[1,2,3,4,5,6,7,8]

37439 // 7！ = 7,说明1~8可以取完7个数字的全排列，只有可能最高位是8，37439 % 7！ = 2159，进入下一轮。nums剩下[1,2,3,4,5,6,7]

2159 // 6! = 2，说明1~7可以取两种，剩下的数中可以保证取两种的最小数是3. 2159 % 6! = 719,剩下[1,2,4,5,6,7]

719//5! = 5，可以取5种，保证取到5种的最小数是7，719%5! = 119，剩下[1,2,4,5,6]

119//4! = 4，可以取4种，保证取到5种的最小数是6，，119%4！=23,剩下[1,2,4,5]

23//3!=3, 可以取3种，保证取到3种的最小数是5, 23%3!=5, 剩下[1,2,4]

5//2!=2,可以取2种，保证取到2种的最小数是4，5%2!=1, 剩下[1,2]

1//1!=1,可以取1种，保证取到1种的最小数是2，1%1!=1, 剩下[1]

1//0!=1,可以取1种，保证取到1种的最小数是1，0%1!=0, 结束

综上，最终结果为983765421

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        nums = []
        for i in range(1, n+1):
            nums.append(str(i))      #['1','2','3',...,'n']
        fact = [0]*n    #阶乘
        fact[0] = 1
        for i in range(1, n):
            fact[i] = i * fact[i-1]
        k -= 1  #偏移
        record = [] #记录
        #n轮循环
        for i in range(n, 0, -1):
            ind = k // fact[i-1]    #确定第i位
            k = k % fact[i-1]    #剩下的数
            record.append(nums[ind])
            nums.remove(nums[ind])  #移出
        return ''.join(record)