小明思考

Just a software engineer
posts - 124, comments - 36, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Subsets

Posted on 2013-05-21 22:50 小明 阅读(2092) 评论(0)  编辑  收藏 所属分类: 数据结构和算法
Problem

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[   [2],   [1],   [1,2,2],   [2,2],   [1,2],   [] ] 

分析:
因为要求结果集是升序排列,所以首先我们要对数组进行排序。

子集的长度可以从0到整个数组的长度。长度为n+1的子集可以由长度为n的子集再加上在之后的一个元素组成。

这里我使用了三个技巧
1。使用了一个index数组来记录每个子集的最大索引,这样添加新元素就很简单。
2。使用了两个变量start和end来记录上一个长度的子集在结果中的起始和终止位置。
3。去重处理使用了一个last变量记录前一次的值,它的初始值设为S[0]-1,这样就保证了和数组的任何一个元素不同。

代码如下:
public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
        Arrays.sort(S);
        
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> indexs = new ArrayList<Integer>();
        result.add(new ArrayList<Integer>());
        indexs.add(-1);
        
        int slen = S.length;
        int start=0,end=0;
        for(int len=1;len<=slen;++len){
            int e = end;
            for(int i=start;i<=end;++i){
                ArrayList<Integer> ss = result.get(i);
                int index = indexs.get(i).intValue();
                int last = S[0]-1;
                for(int j = index+1;j<slen;++j){
                    int v = S[j];
                    if(v!=last){
                        ArrayList<Integer> newss = new ArrayList<Integer>(ss);
                        newss.add(v);
                        result.add(newss);
                        indexs.add(j);
                        ++e;
                        last = v;
                    }
                }
            }
            
            start = end+1;
            end = e;
        }
        return result;
    }
}

只有注册用户登录后才能发表评论。


网站导航: