Python Elegant and Fast Solution


  • 0
    D
    class Solution(object):
        def getPermutation(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: str
            """
            factorials = [1]*n
            for i in range(1, n): factorials[i] = factorials[i-1]*(i+1)
            
            candidates = list(str(x) for x in range(1, n+1))
            ans = ['']
            def collect(remain, kCandidate):
                if kCandidate <= 0: return
                nGroup = factorials[kCandidate-2]
                first_index = (remain-1)/nGroup
                ans[0] += candidates.pop(first_index)
                collect(remain%nGroup, kCandidate-1)
            collect(k, n)
            return ans[0]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.