060 permutation sequence
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
