Permutation Sequence

Question

Given n and k, return the k-th permutation sequence.

Example For n = 3, all permutations are listed as follows:

"123"
"132"
"213"
"231"
"312"
"321"

If k = 4, the fourth permutation is "231"

Note

n will be between 1 and 9 inclusive.

Challenge O(n*k) in time complexity is easy, can you do it in O(n^2) or less?

Thoughts

refer

a1,a2,a3.....an的permutation 如果确定了a1,那么剩下的permutation就有(n-1)!种 所以 a1 = k / (n-1)! k2 = k % (n-1)! a2 = k2 / (n-2)!

要注意的是

• 得到的应该是剩下选择数字的index,而不是value,所以要建一个存储可用数字的array
• 在用完一个数字后要将它从array中删去
• array是0-based index, 那么K也应该减去1变为0-based的

Solution

class Solution:
    """
    @param n: n
    @param k: the k-th permutation
    @return: a string, the k-th permutation
    """
    def getPermutation(self, n, k):
        if not n:
            return ""
        result = ""
        product = 1
        nums = []
        for i in range(0, n):
            nums.append(i+1)
            product *= i+1
        k1 = k - 1 
        for j in range(n, 0, -1):
            product /= j
            a = k1 / product
            result += str(nums[a])
            del nums[a]
            k1 = k1 % product

        return result