Python code of Adeath's idea


  • 0
    H

    The main idea is to determine each number using the feature of lexicographical order.

    class Solution(object):
        def getPermutation(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: str
            """
            if n == 0:
                return ''
            s = [0]*n
            fact =  [1 for i in range(n)]   # calculate factorial for later use
            for i in xrange(n-1):  fact[i+1] = fact[i]*(i+1)    # fact[i] = i!
            num = [i+1 for i in range(n)]   # a list recording remained numbers
            i = 0
            k = k - 1   # for modular operation
            while i < n:
                s[i] = num[k//fact[n-1-i]]
                num.remove(s[i])
                k = k % fact[n-1-i]
                i += 1
            return ''.join([str(x) for x in s])
    

Log in to reply
 

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