Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

子集II

Posted on In , ,
Symbols count in article: 2.5k Reading time ≈ 2 mins.

来自Leetcode第90题子集II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

回溯

判断当前数字和上一个数字是否相同，相同的话跳过即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
List<List<Integer>> an = new ArrayList<>();
int[] num;
public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    this.num = nums;
    helper(0, new ArrayList<>());
    return an;
}

private void helper(int start,List<Integer> tmp){
    an.add(new ArrayList<>(tmp));
    for(int i = start; i < num.length; i++){
        //和上个数字相等就跳过
        if(i > start && num[i] == num[i - 1])
            continue;
        tmp.add(num[i]);
        helper(i + 1,tmp);
        tmp.remove(tmp.size() - 1);
    }
}

迭代

来自

先考虑 0 个数字的所有子串，再考虑 1 个的所有子串，再考虑 2 个的所有子串。而求 n 个的所有子串，就是 【n - 1 的所有子串】和 【n - 1 的所有子串加上 n】。当有重复数字的时候，我们只考虑上一步的新解，算法中用一个指针保存每一步的新解开始的位置即可。

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    ans.add(new ArrayList<>());// 初始化空数组
    Arrays.sort(nums);
    int start = 1; //保存新解的开始位置
    for (int i = 0; i < nums.length; i++) {
        List<List<Integer>> ans_tmp = new ArrayList<>();
        // 遍历之前的所有结果
        for (int j = 0; j < ans.size(); j++) {
            List<Integer> list = ans.get(j);
            //如果出现重复数字，就跳过所有旧解
            if (i > 0 && nums[i] == nums[i - 1] && j < start) {
                continue;
            }
            List<Integer> tmp = new ArrayList<>(list);
            tmp.add(nums[i]); // 加入新增数字
            ans_tmp.add(tmp);
        }

        start = ans.size(); //更新新解的开始位置
        ans.addAll(ans_tmp);
    }
    return ans;
}

还有一种思路，参考这里，当有重复数字出现的时候我们不再按照之前的思路走，而是单独考虑这种情况。

当有 n 个重复数字出现，其实就是在出现重复数字之前的所有解中，分别加 1 个重复数字， 2 个重复数字，3 个重复数字 … 什么意思呢，看一个例子。

1
2
3
4
5
6
7
8
9
10
11
12
数组 [ 1 2 2 2 ] 
[ ]的所有子串 [ ]
[ 1 ] 个的所有子串 [ ] [ 1 ] 
然后出现了重复数字 2，那么我们记录重复的次数。然后遍历之前每个解即可
对于 [ ] 这个解，
加 1 个 2，变成 [ 2 ] 
加 2 个 2，变成 [ 2 2 ]
加 3 个 2，变成 [ 2 2 2 ]
对于 [ 1 ] 这个解
加 1 个 2，变成 [ 1 2 ] 
加 2 个 2，变成 [ 1 2 2 ]
加 3 个 2，变成 [ 1 2 2 2 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<List<Integer>> subsetsWithDup(int[] num) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> empty = new ArrayList<Integer>();
    result.add(empty);
    Arrays.sort(num);

    for (int i = 0; i < num.length; i++) {
        int dupCount = 0;
        //判断当前是否是重复数字，并且记录重复的次数
        while( ((i+1) < num.length) && num[i+1] == num[i]) {
            dupCount++;
            i++;
        }
        int prevNum = result.size();
        //遍历之前几个结果的每个解
        for (int j = 0; j < prevNum; j++) {
            List<Integer> element = new ArrayList<Integer>(result.get(j));
            //每次在上次的结果中多加 1 个重复数字
            for (int t = 0; t <= dupCount; t++) {
                element.add(num[i]); //加入当前重复的数字
                result.add(new ArrayList<Integer>(element));
            }
        }
    }
    return result;
}

位运算

来自