Posted on 2022-11-07 05:08
Uriel 阅读(38)
评论(0) 编辑 收藏 引用 所属分类:
数学 、
闲来无事重切Leet Code
求1-n这n个数字的第k个排列数
直接不断求下一个排列数会TLE，考虑到i个数字的排列数一共i!种，于是对从做到位每一位置i，不断整除剩余数字个数的阶乘，来确定该位数应该填充哪个
1 #60
2 #Runtime: 29 ms
3 #Memory Usage: 13.7 MB
4
5 class Solution(object):
6 def getPermutation(self, n, k):
7 """
8 :type n: int
9 :type k: int
10 :rtype: str
11 """
12 nums = range(1, n + 1)
13 ans = []
14 fac = []
15 nt = 1
16 for i in range(2, n+2):
17 fac.append(nt)
18 nt *= i
19 k -= 1
20 for i in range(n):
21 nt = k // fac[n - i - 2]
22 ans.append(nums[nt])
23 nums.pop(nt)
24 k %= fac[n - i - 2]
25 return ''.join(str(i) for i in ans)