90. Subsets II
题目:
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note:
- Elements in a subset must be in non-descending order.
- 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],
[]
]
题解:
Subsets II, 关键是去重复。我们依然使用跟其他dfs +backtracking类似的方法, 当i > pos && nums[i] == nums[i - 1]的时候,跳过当前重复的元素。
Time Complexity - O(2n), Space Complexity - O(2n)。
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length == 0)
return res;
Arrays.sort(nums);
ArrayList<Integer> list = new ArrayList<>();
dfs(res, list, nums, 0);
return res;
} private void dfs(List<List<Integer>> res, ArrayList<Integer> list, int[] nums, int pos) {
res.add(new ArrayList<Integer>(list)); for(int i = pos; i < nums.length; i++) {
if(i > pos && nums[i] == nums[i - 1])
continue;
list.add(nums[i]);
dfs(res, list, nums, i + 1);
list.remove(list.size() - 1);
}
}
}
二刷:
跟Subsets I唯一不同的地方就是由重复。 和一刷一样,重点在于去重复。我们只需要在每一层遍历的时候,因为最开始sort过, 只要用i > pos && nums[i] == nums[i - 1]来跳过重复的元素就可以了。
Java:
Time Complexity - O(n!), Space Complexity (n2)
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
Arrays.sort(nums);
List<Integer> list = new ArrayList<>();
subsetsWithDup(res, list, nums, 0);
return res;
} private void subsetsWithDup(List<List<Integer>> res, List<Integer> list, int[] nums, int pos) {
res.add(new ArrayList<Integer>(list));
for (int i = pos; i < nums.length; i++) {
if (i > pos && nums[i] == nums[i - 1]) {
continue;
}
list.add(nums[i]);
subsetsWithDup(res, list, nums, i + 1);
list.remove(list.size()- 1);
}
}
}
三刷:
时间复杂度和空间复杂度真的不可以糊弄...看评论里shenhualong的解释比较好,基本的递归分析。 还要继续好好训练思维。 去重复的方法也可以用在其他类似题目里。
这里T(n) = T(n - 1) + T(n - 2) + ... + T(1), 因为 T(n - 1) = T(n - 2) + T(n - 3)... + T(1), 所以T(n) = 2 * T(n - 1),结果就是T(n) = 2n。 对于nums中的每一个数字,我们都要做一个Recursive call,所以这里用了O(n)的时间, 最终结果Time Complexity是 n * 2n。 空间复杂度的话因为我们每次要生成new ArrayList<>(),所以也是2n。
地里stellari大神的帖子分析得特别好,放在reference里了。
Java:
Time Complexity - O(n * 2n), Space Complexity (2n)
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null) return res;
Arrays.sort(nums);
getSubsetsWithDup(res, new ArrayList<Integer>(), nums, 0);
return res;
} private void getSubsetsWithDup(List<List<Integer>> res, List<Integer> list, int[] nums, int pos) {
res.add(new ArrayList<>(list));
for (int i = pos; i < nums.length; i++) {
if (i > pos && nums[i] == nums[i - 1]) continue;
list.add(nums[i]);
getSubsetsWithDup(res, list, nums, i + 1);
list.remove(list.size() - 1);
}
}
}
Reference:
http://blog.csdn.net/linhuanmars/article/details/24286377
https://leetcode.com/discuss/46668/recursive-iterative-manipulation-solutions-explanations
http://www.1point3acres.com/bbs/thread-117602-1-1.html
最新文章
- codeblock 编译googletest
- JUnit4参数的使用
- [转载]我的WCF之旅(1):创建一个简单的WCF程序
- Aoite 系列(02) - 超动感的 Ioc 容器
- MySQL入门(四)
- spring配置属性的两种方式
- xargs 命令
- Eclispe怎么给工作空间下的项目分组
- (十)Linux内核中的常用宏container_of
- 4. Median of Two Sorted Arrays
- shop++ 安装
- Fatal signal 11 (SIGSEGV) at 0xdeadbaad (code=1) 错误 解决方案(android-ndk)
- 使用URLConnection获取网页信息的基本流程
- 利用Azure Automation实现云端自动化运维(2)
- 转:微信开发获取地理位置实例(java,非常详细,附工程源码)
- yii2.0使用之缓存
- CF Educational Codeforces Round 10 D. Nested Segments 离散化+树状数组
- fopen()函数参数
- 详解Vue 非父子组件通信方法(非Vuex)
- spark安装