全排列 II （Python）

全排列 II （Python）

时间复杂度 O(n * n!) 在全排列的基础上加了个重复元素的情况，并且要求结果不能重复

思路：

先对原始列表排序，使得重复元素都靠在一起之后在全排列的基础上剪枝

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: res_list = [] path = [] nums_len = len(nums) # 一个相同大小的标记数组 来标记某个下标是否被选择过 selected = [False for _ in range(nums_len)] def doit(): if len(path) == nums_len: res_list.append(path[:]) return for i in range(nums_len): if not selected[i]: # 因为已经对nums数组排过序了 此时nums[i] == nums[i - 1]表明可能是重复分支 # 但此时包含两种情况 以 [1,1,2] 举例 # 情况1、第一层选择了 i=0处的1 第二层选择了 i=1处的1 这种情况是正常的 不应当排除 # 情况2、第一层选择了 i=1处的1 此时为重复分支 需要跳过 # 所以，仅仅判断 nums[i] == nums[i - 1]仍然不够 # 借助selected数组 # 情况1 nums[i]虽然和num[i - 1]相等 但是selected[i - 1] is True表明nums[i - 1]是在上一层被选走的 此时num[i]可以被正常选择 # 情况2 select[i - 1] is False 表明这就是个重复的情况 应当排除 if i > 0 and nums[i] == nums[i - 1] and not selected[i - 1]: continue # 标记选过 selected[i] = True # 添加值 path.append(nums[i]) doit() # 回滚 path.pop() selected[i] = False # 先排序保证重复元素靠在一起 这样就可以看nums[i] 是否和nums[i - 1] 相等来判断是否重复 nums.sort() doit() return res_list

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。