leetcode_subsets_ii

发表于

难度：Medium

解题思路：需要先排序。重复的时候，只需要在后半段增加。

1 2 2 2
[]
[] [1]
[] [1] [2] [1 2]
[] [1] [2] [1 2] [2 2] [1 2 2]    //只需要增加后两个
[] [1] [2] [1 2] [2 2] [1 2 2] [2 2 2] [1 2 2]    //只需要增加后两个

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        if(nums.size()==0)  return ret;
        ret.push_back(vector<int>{});
        ret.push_back(vector<int>{nums[0]});
        int half_size = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] != nums[i-1])
            {
                size_t sz = ret.size();
                for(int j = 0; j <  sz; j++)
                {
                    vector<int> tmp = ret[j];
                    tmp.push_back(nums[i]);
                    ret.push_back(tmp);
                }
                half_size = ret.size()/2;
            }
            else
            {
                size_t sz = ret.size();
                for(int j = ret.size()-half_size; j < sz; j++)
                {
                    vector<int> tmp = ret[j];
                    tmp.push_back(nums[i]);
                    ret.push_back(tmp);   
                }
            }
        }
        return ret;
    }
};

运行结果：9ms，超过31.27%