[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 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

【面试虐菜】—— JAVA面试题(3)

1 throws与throw的区别 解析:throws和throw是异常处理时两个常见的关键字,初级程序员常常容易正确理解throw和throws的作用和区别,...

1708
来自专栏Android干货园

Kotlin中级(9)- - - Kotlin类之数据类、密封类、内部类.md

上面的代码我们可以看到结构出来的变脸可以直接拿来用,比如数据体Leaf中的size属性,componentN函数群会按照数据体Leaf中属性声明的顺序,从com...

622
来自专栏软件开发 -- 分享 互助 成长

(虚)继承类的内存占用大小

(虚)继承类的内存占用大小 首先,平时所声明的类只是一种类型定义,它本身是没有大小可言的。 因此,如果用sizeof运算符对一个类型名操作,那得到的是具有该类...

1708
来自专栏Java大联盟

Java面试手册:核心基础-2

4.abstract的method是否可同时是static,是否可同时是native,是否可同时是synchronized?

451
来自专栏java学习

面试题55(考察求职者对类的声明的掌握)

(不定项选择题)在Java中下面Class的声明哪些是错误的? A public abstract final class Test { abstract ...

3295
来自专栏desperate633

浅谈javascript中的的闭包作用域链引出闭包利用闭包突破作用域链的三种方法小结

闭包可以说是javascript中最令人迷惑的概念了。需要我们在实践中去慢慢理解,在实际编码中,由于闭包的效率和会产生大量无法销毁的内存,所以原则是尽量少使用闭...

571
来自专栏恰同学骚年

数据结构基础温故-4.树与二叉树(中)

在上一篇中,我们了解了树的基本概念以及二叉树的基本特点和代码实现,还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是,由于递归需要系统堆栈,所以空间消耗要...

681
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day6 Java字符串

  字符串,是我们最常用的类型,每个用双引号来表示的串都是一个字符串。Java中的字符串是一个预定义的类,跟C++ 一样叫String,而不是Char数组。至于...

1778
来自专栏IMWeb前端团队

Es6浅析

Es6浅析 Babel 是一个 JavaScript编译器,它可以把我们编写的符合 ECMAScript 6 标准的代码完美地转换为 ECMAScript 5 ...

1777
来自专栏烂笔头

Python标准库笔记(3) — datetime模块

目录[-] datetime模块提供了简单和复杂的方式用于操纵日期和时间的类。虽然支持日期和时间运算,但实现的重点是为了输出格式化和操作高效地提取属性。 ...

3556

扫码关注云+社区