[LeetCode] 90. Subsets II

【原题】 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],
  []
]

【解释】 作为Subsets一题的follow up,要求在给定序列有重复元素的情况下求出所有子集。 【思路】 在这里,由于元素互异,所有可以不排序。但在有重复元素的情况下,由于重复的元素有可能不在一块,所以一定要排序。基本的思路为不重复添加已经添加过得子集: 比如给定序列{1,2,2} 初始化:{{}} 第一次:{{},{1}} 第二次:{{},{1},{2},{1,2}} 第三次:{{},{1},{2},{1,2}},遇到重复的元素,加粗的子集是上一个2添加形成的,当再次遇到2时,需要添加到之前2没有添加的子集即加粗的部分。最终形成{{},{1},{2},{1,2},{2,2},{1,2,2}}

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> results=new ArrayList<List<Integer>>();
        results.add(new ArrayList<Integer>());
        int preEnd=0;
        Arrays.sort(nums);//必须排序
        for(int i=0;i<nums.length;i++){
            int n=results.size();
            int start;
            if(i>0&&nums[i]==nums[i-1]) start=preEnd;//若有重复,则不重复添加已经添加过的子集,从preEnd开始添加
            else start=0;
            List<Integer> tmp = null;
            for(int j=start;j<n;j++){
                tmp=new ArrayList<>(results.get(j));
                tmp.add(nums[i]);
                results.add(tmp);               
            }
            preEnd=n;
        }
        return results;

    }
}

也可以使用之前的方法,然后在加入集合的时候,判断该子集是否在集合当中,这孩子能够方法效率不高,且和Subsets类似这里不再赘述。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

基础算法|4 简单选择排序

我们之前已经了解了三种基础算法,分别为二分查找算法,冒泡排序算法,以及直接插入排序算法。俗话说得好,温故而知新,所以现在就让我们简单回顾一下之前的三种算法吧。...

1093
来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

3287
来自专栏韦弦的偶尔分享

Swift 旋转数组 - LeetCode

例如,如果 n = 7 , k = 3,给定数组 [1,2,3,4,5,6,7] ,向右旋转后的结果为 [5,6,7,1,2,3,4]。

1095
来自专栏赵俊的Java专栏

LeetCode 557 Reverse Words in a String III

首先按照空格对字符串进行分隔,然后将每个单词进行翻转后再拼接回字符串即可,需要注意拼接时记得加空格,但最后一个单词不需要加。

601
来自专栏desperate633

[编程题] 集合代码

小易最近在数学课上学习到了集合的概念,集合有三个特征:1.确定性 2.互异性 3.无序性.小易的老师给了小易这样一个集合:S = { p/q | w ≤ p ≤...

731
来自专栏章鱼的慢慢技术路

蓝桥杯题库基础练习:进制转换

1804
来自专栏我的技术专栏

数据结构图文解析之:二分查找及与其相关的几个问题解析

1422
来自专栏有趣的Python

玩转算法面试:(三)LeetCode数组类问题

数组中的问题其实最常见。 排序:选择排序;插入排序;归并排序;快速排序 查找:二分查找法 数据结构:栈;队列;堆 …… 如何写出正确的程序 建立一个基...

5374
来自专栏数据结构与算法

4939 欧拉函数

 时间限制: 1 s  空间限制: 1000 KB  题目等级 : 钻石 Diamond 题解 题目描述 Description 输入一个数n,输出小于n且与n...

3227
来自专栏和蔼的张星的图像处理专栏

60. 搜索插入位置二分查找__细节

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。

1043

扫码关注云+社区