从后往前遍历,找到第一个a[i]>a[i-1]的元素,然后在nums[a:]中找到最小的大于a[i-1]的元素,替换a[i-1],此时nums[a:]依然为降序,反转即可
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
def reverse(i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
for i in range(len(nums)-1, 0, -1):
if nums[i] > nums[i-1]:
j = i
while j<len(nums) and nums[j] > nums[i-1]:
j += 1
nums[i-1], nums[j-1] = nums[j-1], nums[i-1]
reverse(i, len(nums)-1)
return
reverse(0, len(nums)-1)
return
- 暴力:利用下一个排列逐步求更大的最小排列,直到第k个
- 回溯+剪枝:确定第一个数后,后面的数的可能性有n!种,如果小于k,那么确定的第一个数不是答案的一部分,因此第一个数应该是nums的第二个,再计算后面的数的可能性有没有超过k,没有的话,便可以确定第一位数,以此类推
# 暴力-7500ms
class Solution:
def getPermutation(self, n: int, k: int) -> str:
nums = list(range(1, n+1))
def helper(nums):
for i in range(len(nums)-1, 0, -1):
if nums[i] > nums[i-1]:
j = i
while j<len(nums) and nums[j]>nums[i-1]:
j += 1
nums[i-1], nums[j-1] = nums[j-1], nums[i-1]
tmp = nums[i:][::-1]
return nums[:i] + tmp
for i in range(1, k):
nums = helper(nums)
return ''.join([str(n) for n in nums])
# 回溯+剪枝-40ms
import math
class Solution:
def getPermutation(self, n: int, k: int) -> str:
# 剪枝
nums = list(range(1, n+1))
ans = ''
count = 0
def dfs(path, ns):
nonlocal ans, count, k
if len(path)==len(nums):
ans = ''.join([str(n) for n in path])
count = 1
return
for i, n in enumerate(ns):
if not count:
if math.factorial(len(ns[:i]+ns[i+1:]))>=k:
path.append(n)
ns_ = ns[:i] + ns[i+1:]
dfs(path, ns_)
path.pop()
else:
k -= math.factorial(len(ns[:i]+ns[i+1:]))
else:
break
dfs([], nums)
return ans
# 回溯
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# 回溯DFS
ans = []
def dfs(path, ns):
if len(path) == len(nums):
ans.append(path[:])
return
for i, n in enumerate(ns):
path.append(n)
ns_ = ns[:i] + ns[i+1:]
dfs(path, ns_)
path.pop()
dfs([], nums)
return ans
# DP
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return None
dp = [[] for i in range(len(nums))]
dp[0] = [[nums[0]]]
for i in range(1, len(nums)):
# 状态转移
for ans in dp[i-1]:
# 尾插
dp[i].append(ans+[nums[i]])
# 前插
for j in range(len(ans)):
dp[i].append(ans[:j]+[nums[i]]+ans[j:])
return dp[-1]
- 回溯:和全排列的不同点在于数组有重复数字,因此回溯过程需要对重复出现的进行剪枝,需要进行排序,将重复数字聚拢在一起
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# 回溯
ans = []
nums.sort()
def dfs(path, ns):
if len(path) == len(nums):
ans.append(path[:])
return
for i, n in enumerate(ns):
if i==0 or ns[i] != ns[i-1]:
path.append(n)
ns_ = ns[:i] + ns[i+1:]
dfs(path, ns_)
path.pop()
dfs([], nums)
return ans