找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1511|回复: 3
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Subsets II】-【刷题第一弹 2014】

[复制链接]

24

主题

9

精华

602

积分

超级会员

Rank: 4

积分
602
发表于 10-23-2014 06:25 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:45 AM 编辑

快速通道:
https://oj.leetcode.com/problems/subsets-ii/

=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================


思路:辅助函数首先将当前的集合curr加入到结果集res中,然后对kn-1做一个循环,判断的条件是i==k||num【i】!=num[i-1]【i】,略去重复的数。

java代码:
  1. public List<List<Integer>> subsetsWithDup(int[] num) {
  2.         List<List<Integer>> res = new ArrayList<List<Integer>>();
  3.         if(num==null||num.length==0){
  4.             res.add(new ArrayList<Integer>());
  5.             return res;
  6.         }
  7.         Arrays.sort(num);
  8.         List<Integer> curr = new ArrayList<Integer>();
  9.         subsetsWithDup(res,curr,num,0);
  10.         return res;
  11.     }
  12.    
  13.     public void subsetsWithDup(List<List<Integer>> res,List<Integer> curr,int[] num,int k){
  14.         res.add(curr);//@bugfree add the current set;
  15.         for(int i=k;i<num.length;++i){
  16.             if(i==k||num【i】!=num[i-1]){//@bugfree this is the key
  17.                 List<Integer> clone = new ArrayList<Integer>(curr);
  18.                 clone.add(num【i】);
  19.                 subsetsWithDup(res,clone,num,i+1);
  20.             }
  21.         }   
  22.     }
复制代码



复杂度:O(2^n)

本帖被以下淘专辑推荐:

7

主题

3

精华

237

积分

高级会员

Rank: 3Rank: 3

积分
237
发表于 10-23-2014 07:13 PM | 显示全部楼层
楼主可以写一份iterative的代码吗?谢谢啦
回复 支持 反对

使用道具 举报

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 11-20-2014 03:42 PM | 显示全部楼层
递归 time O(2^n) space O(n)--迭代 同
  1.     public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
  2.         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  3.         if(num==null || num.length==0) return res;
  4.         Arrays.sort(num);
  5.         ArrayList<Integer> tmp = new ArrayList<Integer>();
  6.         res.add(new ArrayList<Integer>());
  7.         generate(res, 0, num, tmp);
  8.         return res;
  9.     }
  10.     public void generate(ArrayList<ArrayList<Integer>> res, int index, int[] num, ArrayList<Integer> tmp){
  11.             for(int i=index; i<num.length; i++){
  12.                 if(i==index || num[i]!=num[i-1]){
  13.                     tmp.add(num[i]);
  14.                     ArrayList<Integer> new_list = new ArrayList<Integer>();
  15.                     new_list.addAll(tmp);
  16.                     res.add(new_list);
  17.                     generate(res, i+1, num, tmp);
  18.                     tmp.remove(tmp.size()-1);
  19.                 }
  20.             }
  21.     }
复制代码
  1.     public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
  2.         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  3.         ArrayList<Integer> tmp = new ArrayList<Integer>();
  4.         Arrays.sort(num);
  5.         res.add(tmp);
  6.         if(num==null || num.length == 0) return null;
  7.         int cur = 1;
  8.         int pre = 1;
  9.         for(int i = 0; i<num.length; i++){
  10.             int j = cur-1;
  11.             while(j>=0){
  12.                 if(i!=0 && num[i] == num[i-1] && j==pre-1){
  13.                     break;
  14.                 }
  15.                 tmp = res.get(j);
  16.                 ArrayList<Integer> new_list = new ArrayList<Integer>();
  17.                 new_list.addAll(tmp);
  18.                 new_list.add(num[i]);
  19.                 res.add(new_list);
  20.                 j--;
  21.             }
  22.             pre = cur;
  23.             cur = res.size();
  24.         }
  25.         return res;
  26.     }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表