classSolution(object):defgetPermutation(self,n,k):""" :type n: int :type k: int :rtype: str """# if n=3, we have (3-1)! start with 1/2/3, and for 1/2/3+left part, left part have (2-1)! start with what is left# check the region that the sequence number falls in and get the starting digitelements=range(1,n+1)NN=reduce(lambdax,y:x*y,elements)# n!k,result=k-1,''# k is starting digitwhilelen(elements)>0:NN=NN/len(elements)# the length of the remain part, NN / len(elements)=(n-1)!i,k=k/NN,k%NN# i is index of the value of this loop, k is how many k leftresult+=str(elements.pop(i))# delete the used item from elementreturnresultif__name__=="__main__":answer=Solution()printrepr(answer.getPermutation(3,5))
近期评论