前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[LeetCode] 90. Subsets II

[LeetCode] 90. Subsets II

作者头像
用户1148830
发布2018-01-03 17:42:27
5470
发布2018-01-03 17:42:27
举报
文章被收录于专栏:来自地球男人的部落格

【原题】 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:

代码语言:javascript
复制
[
  [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}}

代码语言:javascript
复制
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类似这里不再赘述。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年06月15日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档