Posted on 2022-11-07 05:08
Uriel 閱讀(77)
評論(0) 編輯 收藏 引用 所屬分類:
數(shù)學(xué) 、
閑來無事重切Leet Code
求1-n這n個(gè)數(shù)字的第k個(gè)排列數(shù)
直接不斷求下一個(gè)排列數(shù)會(huì)TLE，考慮到i個(gè)數(shù)字的排列數(shù)一共i!種，于是對從做到位每一位置i，不斷整除剩余數(shù)字個(gè)數(shù)的階乘，來確定該位數(shù)應(yīng)該填充哪個(gè)
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)