题目描述
这是 LeetCode 上的 90. 子集 II ,难度为 中等。
Tag : 「位运算」、「回溯算法」、「状态压缩」、「DFS」
给你一个整数数组 nums
,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
- $1
- $-10
回溯解法(Set)
由于是求所有的方案,而且数据范围只有 $10$,可以直接用爆搜来做。
同时由于答案中不能包含相同的方案,因此我们可以先对原数组进行排序,从而确保所有爆搜出来的方案,都具有单调性,然后配合 Set
进行去重。
代码:
class Solution {
public List> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
Set> ans = new HashSet();
List cur = new ArrayList();
dfs(nums, 0, cur, ans);
return new ArrayList(ans);
}
/**
* @param nums 原输入数组
* @param u 当前决策到原输入数组中的哪一位
* @param cur 当前方案
* @param ans 最终结果集
*/
void dfs(int[] nums, int u, List cur, Set> ans) {
// 所有位置都决策完成,将当前方案放入结果集
if (nums.length == u) {
ans.add(new ArrayList(cur));
return;
}
// 选择当前位置的元素,往下决策
cur.add(nums[u]);
dfs(nums, u + 1, cur, ans);
// 不选当前位置的元素(回溯),往下决策
cur.remove(cur.size() - 1);
dfs(nums, u + 1, cur, ans);
}
}
- 时间复杂度:排序复杂度为 $O(nlog{n})$,爆搜复杂度为 $(2^n)$,每个方案通过深拷贝存入答案,复杂度为 $O(n)$。整体复杂度为 $(n times 2^n)$
- 空间复杂度:总共有 $2^n$ 个方案,每个方案最多占用 $O(n)$ 空间,整体复杂度为 $(n times 2^n)$
回溯解法
我们知道使用 Set
虽然是 $O(1)$ 操作,但是只是均摊 $O(1)$。
因此我们来考虑不使用 Set
的做法。
我们使用 Set
的目的是为了去重,那什么时候会导致的重复呢?
其实就是相同的元素,不同的决策方案对应同样的结果。
举个🌰,[1,1,1] 的数据,只选择第一个和只选择第三个(不同的决策方案),结果是一样的。
因此如果我们希望去重的话,不能单纯的利用「某个下标是否被选择」来进行决策,而是要找到某个数值的连续一段,根据该数值的选择次数类进行决策。
还是那个🌰,[1,1,1] 的数据,我们可以需要找到数值为 1 的连续一段,然后决策选择 0 次、选择 1 次、选择 2 次 … 从而确保不会出现重复
也就是说,将决策方案从「某个下标是否被选择」修改为「相同的数值被选择的个数」。这样肯定不会出现重复,因为 [1,1,1] 不会因为只选择第一个和只选择第三个产生两个 [1] 的方案,只会因为 1 被选择一次,产生一个 [1] 的方案。
代码:
class Solution {
public List> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List> ans = new ArrayList();
List cur = new ArrayList();
dfs(nums, 0, cur, ans);
return ans;
}
/**
* @param nums 原输入数组
* @param u 当前决策到原输入数组中的哪一位
* @param cur 当前方案
* @param ans 最终结果集
*/
void dfs(int[] nums, int u, List cur, List> ans) {
// 所有位置都决策完成,将当前方案放入结果集
int n = nums.length;
if (n == u) {
ans.add(new ArrayList(cur));
return;
}
// 记录当前位置是什么数值(令数值为 t),并找出数值为 t 的连续一段
int t = nums[u];
int last = u;
while (last
- 时间复杂度:排序复杂度为 $O(nlog{n})$,爆搜复杂度为 $(2^n)$,每个方案通过深拷贝存入答案,复杂度为 $O(n)$。整体复杂度为 $(n times 2^n)$
- 空间复杂度:总共有 $2^n$ 个方案,每个方案最多占用 $O(n)$ 空间,整体复杂度为 $(n times 2^n)$
状态压缩(Set)
由于长度只有 10,我们可以使用一个 int
的后 $10$ 位来代表每位数组成员是否被选择。
同样,我们也需要先对原数组进行排序,再配合 Set
来进行去重。
代码:
class Solution {
public List> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
Set> ans = new HashSet();
List cur = new ArrayList();
// 枚举 i 代表,枚举所有的选择方案状态
// 例如 [1,2],我们有 []、[1]、[2]、[1,2] 几种方案,分别对应了 00、10、01、11 几种状态
for (int i = 0; i > j) & 1;
if (t == 1) cur.add(nums[j]);
}
// 将当前方案中加入结果集
ans.add(new ArrayList(cur));
}
return new ArrayList(ans);
}
}
- 时间复杂度:排序复杂度为 $O(nlog{n})$,爆搜复杂度为 $(2^n)$,每个方案通过深拷贝存入答案,复杂度为 $O(n)$。整体复杂度为 $(n times 2^n)$
- 空间复杂度:总共有 $2^n$ 个方案,每个方案最多占用 $O(n)$ 空间,整体复杂度为 $(n times 2^n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.90
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
本文由mdnice多平台发布
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
前言 搜索引擎是对数据的检索,而数据总体分为两种:结构化数据和非结构化数据。而对于结构化数据,因为他们具有特定的结构,所以一般都是可以通过关系型数据库MySQL/oracle的二维表的方式存储和搜索,也可以建立索引。 对于非结构化数据,对他们进行搜索主…