Python I think this is clean code. with some of my explanation


  • 5
    W

    If we have n numbers then the total combinations would be factorial(n) which means same starting number should have (n - 1)! sequences.

    If we do k mod (n - 1)! then we can get the corresponding starting number and append to the result.

    Note that we need to maintain another array to mark visited numbers(I take remove to make sure we will not revisit the number again, each remove takes O(n) time )

    The total time complexity would be O(n^2).

    class Solution(object):
        def getPermutation(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: str
            """
            nums = map(str, range(1, 10))
            k -= 1
            factor = 1
            for i in range(1, n):
                factor *= i
            res = []
            for i in reversed(range(n)):
                res.append(nums[k / factor])
                nums.remove(nums[k / factor])
                if i != 0:
                    k %= factor
                    factor /= i
            return "".join(res)

  • 1
    L

    In case of k is large number,it's better to preprocess k before loop
    k = k % (factor * n).


  • 0

    You are really smart man :D


Log in to reply
 

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