问题描述:
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2]
, a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
原问题链接:https://leetcode.com/problems/subsets-ii/
问题分析
这个问题有一个比较简单的思路,就是基于前面subsets问题的基础,在每次往列表里加入元素的时候判断一下是否有现存的元素来去除重复。这种方式的代码实现如下:
public class Solution { public List<List<Integer>> subsetsWithDup(int[] num) { Arrays.sort(num); List<List<Integer>> lists = new ArrayList<List<Integer>>(); for(int i = 0; i < 1 << num.length; i++) { List<Integer> list = new ArrayList<Integer>(); for(int j = 0; j < num.length; j++) { if((i & (1 << j)) > 0) list.add(num[j]); } if(!lists.contains(list)) lists.add(list); } return lists; } }
这种方式是基于求所有子集方法的代码加了个重复检查的部分。但是在出现重复元素比较多的情况下会不断的要去list里查找比较,所以性能会相对比较低。
除了上述的办法,其实我们还有一种思路。就是对于一个数组来说,它可以有一种递推的情况。最开始当这个数组有0个元素的时候,它所有的取值就是0个,也就是说我们返回一个空的数组作为它的子集。
而如果这时候有1个元素了呢,那么它就是在原来的基础上增加一个包含有这个元素本身的子集。在这里我们就有了两个集合元素:[[], [1]] 。也就是空集和这个元素本身。如果对这个过程做更加一般化的推导的话,就会发现对于第i个元素来说,它前面的i - 1个元素构成的集合我们已经得到了。相当于已经有了前面i - 1个元素构成的所有子集,那么这个子集对于第i个元素来说相当于是不选择第i个的所有情况。那么对于加入第i个元素的情况来说,就需要将这个元素依次增加到原来的每个元素里作为新的选择情况。
这样,我们就得到了一个一般情况下生成集合子集的一个思路。就是首先取空集放到一个列表里。然后每次取一个元素和这个列表里的元素合并,新生成的结果也加入到列表里。这样列表不断累加,生成了所有的情况。但是在这个问题里,我们还有重复的元素,该怎么来处理呢?
在这里我们需要稍微用一个技巧,首先将这些数组元素排序。这样相同的元素就肯定都挨在一起了。每次取一个位置的元素时就和它前面的元素去比较,如果这个元素和前面的元素不同,说明是一个新的元素,按照前面的思路,需要从头开始去和每个元素合并生成新结果。否则说明它的前一个元素已经和之前的那些元素生成了一遍结果集,它就不应该再去重新生成一遍了,而是应该从它前一个元素和之前所有结果开始归并的地方继续进行合并。要实现这一点,需要用一个变量来记录每次前一个元素合并完之后所在的位置。然后在下一个循环开头的时候判断一下,如果nums[i] != nums[i - 1],则将开始的部分begin = 0,否则就保持begin = 上次合并完所在的位置。
详细的代码实现如下:
public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); result.add(new ArrayList<>()); int begin = 0; for(int i = 0; i < nums.length; i++){ if(i == 0 || nums[i] != nums[i - 1]) begin = 0; int size = result.size(); for(int j = begin; j < size; j++){ List<Integer> cur = new ArrayList<>(result.get(j)); cur.add(nums[i]); result.add(cur); } begin = size; } return result; } }
这种方法因为减少了对重复元素的检查和数组扫描,它的效率会相对高一些。不过由于子集的生成本身在时间复杂度上是指数级别的。它的时间复杂度依然是O(2 ** n) 。
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
单词搜索II(判断一批单词是否出现在给定的网格中) 3. 二分查找 LeetCode69 : 求x的平方根 LeetCode704 : 标准的二分查找代码模板 4. 剪枝 LeetCode51、LeetCode51NQueen : N皇后问题 LeetCode37 : 求解数独问题 5. ...
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
LeetCode 101:和你一起你轻松刷题(C++)
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
Leetcode:Leetcode提交
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
leetcode:LeetCode题解