060._permutation_sequence.md

###60. Permutation Sequence

题目: https://leetcode.com/problems/permutation-sequence/

难度:

Medium

偷懒，用46的方法，会超时

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        self.result = []
        s = ""
        for i in range(1, n+1):
          s += str(i)
        self.recPermute("",s,k)
        return self.result[-1]
        

    def recPermute(self, sofar, rest, k):
      if rest == "":
        if len(self.result) == k:
          return
        self.result.append(sofar)
      else:
        for i in xrange(len(rest)):
          nnext = sofar + rest[i]
          remaining = rest[:i] + rest[i+1:]
          self.recPermute(nnext, remaining, k)

然后其实有规律的，比如

1 "123"
2 "132"
3 "213"
4 "231"
5 "312"
6 "321"

是第n个数 + 余下的n-1个数的permutation

k = 1 就是所有的顺序排列 k = n! 是所有的逆序排列

对于余下的也是递归，比如

k < (n-1)! 1 + (n-1)个数的全排列的第k个 k < 2*(n-1)! 2 + (n-1)个数的顺序全排列的第k个

发现思路对了，但是implement还有点困难.

看了一个最为精妙的解法

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        seq, k, fact = '', k-1, math.factorial(n-1)
        perm = [i for i in range(1, n+1)]
        for i in reversed(xrange(n)):
            curr = perm[k/fact]
            seq += str(curr)
            perm.remove(curr)
            if i > 0:
                k %= fact
                fact /= i
        return seq