给出n和k 求由1-n的数字组成的第k大的数 本来想尝试一个个列举的，然而超时了。因为是n的阶乘的复杂度。 首位为1的排列总共有(n-1)!个 已知前两位的排列共有(n-2)!个 那么第k个排列 k//(n-1)!就是第一个数取当前剩余数字的第几个 k%(n-1)!//(n-2)!就是第二个数取当前剩余数字的第几个
class Solution(object): def getPermutation(self, n, k): """ :type n: int :type k: int :rtype: str """ res = '' nums = [i for i in range(1,n+1)] for i in range(n-1,0,-1): base = math.factorial(i) current = 0 while k > base: k -= base current += 1 res += str(nums[current]) nums.pop(current) res += str(nums[0]) return res