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

相关文章

来自专栏韦弦的微信小程序

Swift 字符串中的第一个唯一字符 - LeetCode

1、将字符串转为数组 2、循环字符串数组,将字符作为键,索引作为值存入字典 3、存入字典时先判断是否已经存在,已存在则将值置位-1 4、循环字典,拿到所有...

831
来自专栏老马说编程

(27) 剖析包装类 (中) / 计算机程序的思维逻辑

本节继续探讨包装类,主要介绍Integer类,下节介绍Character类,Long与Integer类似,就不再单独介绍了,其他类基本已经介绍完了,不再赘述。 ...

20310
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day06-知识点回顾与练习

Java基础-day06-知识点回顾与练习 1.求和案例 ? 实现代码: package StudentJavaSEday06; public class De...

2973
来自专栏吾爱乐享

java之学习正则表达式的分组功能及案例

1192
来自专栏Java编程

Java正则表达式详解

Java 提供了功能强大的正则表达式API,在java.util.regex 包下。本教程介绍如何使用正则表达式API。

7300
来自专栏较真的前端

关于数字的前端面试题

2576
来自专栏IMWeb前端团队

JavaScript强化教程——sort() 方法

本文作者:IMWeb 王军 原文出处:IMWeb社区 未经同意,禁止转载 本文为 H5EDU 机构官方 HTML5培训 教程,主要介绍:JavaScr...

1755
来自专栏代码世界

Python基础数据类型之集合以及其他和深浅copy

一、基础数据类型汇总补充 list  在循环一个列表时,最好不要删除列表中的元素,这样会使索引发生改变,从而报错(可以从后向前循环删除,这样不会改变未删元素的索...

2919
来自专栏大闲人柴毛毛

动态规划法(二)——弗洛伊德算法

问题描述 给定一个带权有向图,计算任意两结点间的最短路径。 迪杰斯特拉算法可以计算指定起点到所有结点的最短路径长度,因此分别对每个结点使用一次迪杰斯特拉...

3707
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(7) - 简单排序总结

1403

扫码关注云+社区