Description
The set [1,2,3,...,*n*] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123""132""213""231""312""321"
Given n and k, return the kth permutation sequence.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Solutions
1. Backtracking
全排会超时！
# Time: O(n^2)
# Space: O(n)
class Solution:
def getPermutation(self, n: int, k: int) -> str:
res = []
visited = set()
self.dfs(n, k, visited, '', res)
return res[k-1]
def dfs(self, n, k, visited, path, res):
# add this, TLE too
if k <= len(res):
return
if n == len(path):
res.append(path)
return
for i in range(1, n+1):
if i in visited:
continue
visited.add(i)
self.dfs(n, k, visited, path + str(i), res)
visited.remove(i)
# Time Limit Exceeded
# 85/200 cases passed (N/A)
# Testcase
# 9
# 331987
举个例子，n = 4，k = 9 时，有：
1234
1243
1324
1342
1423
1432
2134
2143
2314 <= k = 9
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
根本不需要从 1 开始全排，因为从 1 开始全排的只有 3!=6 个数，那么这里可以优化！
# Time: O(n^2)
# Space: O(n)
class Solution:
def getPermutation(self, n: int, k: int) -> str:
self.k = k
def backtrack(path, remain):
if not remain:
self.k -= 1
if self.k == 0:
return path
return ''
for i in range(len(remain)):
if self.k > math.factorial(len(remain)-1):
self.k -= math.factorial(len(remain)-1)
continue
ans = backtrack(path + remain[i], remain[:i]+remain[i+1:])
if ans:
return ans
return ''
nums = list(map(str, range(1, n+1)))
return backtrack('', nums)
# 200/200 cases passed (32 ms)
# Your runtime beats 78.87 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)