赞
踩
题目难度: 中等
今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复
剑指offer2
就能看到该系列当前连载的所有文章了, 记得关注哦~
给定一个可包含重复数字的整数集合 nums ,按任意顺序 返回它所有不重复的全排列。
[1,3,1]
, 假设两个 1 分别叫 a1 和 b1, 那么 a1->b1->3 和 b1->a1->3 形成的排列就会重复, 都是[1,1,3]
{key:cnt}
[1,1,3]
O(N!)
: 最差情况下 N 个数字各不相同, 排列就有 N!
种O(N)
: 计数字典和 key 列表需要存储最多 N 个元素, 而递归栈在最差情况下长度同样是 Nclass Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# 方法1: 计数字典+dfs(perm)
res = []
# 将原始数组转换成计数字典
cnts = collections.Counter(nums)
def dfs(perm):
if len(perm) == len(nums):
# 当前排列长度等于原始数组长度, 将其加入最终结果中
res.append(perm)
return
for key in cnts:
if cnts[key] > 0:
# 当前key的计数大于0, 可以追加到排列中
# 先尝试追加当前key, 将其计数减1并追加到当前排列中
cnts[key] -= 1
dfs(perm + [key])
# 将其计数恢复, 代表暂不追加当前key
cnts[key] += 1
# 初始排列是空的, 在递归过程中会逐步往里面加数字
dfs([])
return res
[1,2,3]->[1,3,2]->[2,1,3]->[2,3,1]->[3,1,2]->[3,2,1]
, 这样就能保证得到每个不重复的排列O(N*N!)
: N 个数字各不相同, 排列就有 N!
种, 从当前排列转入下一个排列需要 O(N)
时间O(1)
: 只使用了几个常数空间的变量 (不考虑输出结果集)class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# 方法2: 迭代getNext
res = []
n = len(nums)
def getNext(nums):
for i in range(n - 1)[::-1]:
# 从后向前查找
if nums[i] < nums[i + 1]:
# 找到目标数字了, 接下来找后面部分中大于nums[i]且最接近它的数字
j = i + 1
while j < n and nums[j] > nums[i]:
j += 1
# 此时nums[j]<=nums[i], 将它减1后的nums[j]就是后面部分中大于nums[i]且最接近它的数字, 它需要和nums[i]互换
j -= 1
# 单独拿出新的右边部分(已经将下标i和j互换了), 肯定严格按照降序排列
right = nums[i + 1 : j] + [nums[i]] + nums[j + 1 :]
# 将三部分拼接起来, 注意右边部分要逆序, 这样就变成升序排列
return nums[:i] + [nums[j]] + right[::-1]
# 没找到下一个排列, 说明当前排列就是顺序最大的了, 直接返回None
return None
# 先拿到顺序最小的排列
nums.sort()
while nums:
res.append(nums)
nums = getNext(nums)
return res
大家可以在下面这些地方找到我~
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/1005058
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。