Skip to content

Latest commit

 

History

History
 
 

089. Subsets II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题有两个思路:一个就是基于 [63. Subsets](../63. Subsets) 的方案,只需要用一个 set 存储最后结果即可,(或者手动去重(unique))。

这次我采用了另一种思路,即,从根本上避免重复项的插入。

按照题意,假如存在重复项:[1,2,2], 我们构造一个 vector<vector<int>> ret, 并初始化即赋予肯定有的一个 subset: []

vector<vector<int>> ret{{}};
// 遍历 S
for (size_t i=0; i<S.size(); ++i)
    // 假如没有重复项这回事,我们希望遵循以下规律组建 subset
    // i == 0 (S[i] == 1) : [] -> [],[1]    (size == 1)
    //                      ^         ^
    //                      1         *
    // i == 1 (S[i] == 2) : [],[1] -> [],[1],[2],[1,2]  (size == 2)
    //                      ^   ^             ^    ^
    //                      2   2             *    *
    // i == 2 (S[i] == 2) : [],[1],[2],[1,2] -> [],[1],[2],[1,2],[2],[1,2],[2,2],[1,2,2]    (size == 4)
    //                      ^   ^   ^    ^                       ^     ^     ^      ^
    //                      2   2   2    2                       *     *     *      *
    //                                                          !!!   !!!
    // 按照上述步骤,很明显发现了存在重复项的插入(!!!),如何避免呢?
    // 从重复项的产生入手观察,[2]和[1,2] 两个重复项是对 []和[1] 插入 2 产生的。而在此之后的插入,并不会产生重复项。
    // 这个 2 又是怎么来的呢?这个例子不好,有太多的 2,容易迷惑,其实用别的例子试试可以看出,2 代表的是上一次迭代的 size
    // 而这个 size 是什么?这就很明显了,就是我们生成 subset 需要的迭代次数。
    // 假设 S[i] 是一个重复值,可以看出,ret中[上一次size]项之前的元素插入 S[i] 会产生重复项,而[上一次size]项之后的则不会。
    // 所以[插入]工作,应该有一个范围,设起始为 b, 结束为 e,有:
    size_t b = i && S[i] == S[i-1] ? e  : 0;
    //         ^         ^           ^    ^
    //        i>=1   出现重复项 上次的结束 重新开始
    size_t e = ret.size();
    for (; b < e; ++b)
        ret.insert(ret.end(), ret[b])->push_back(S[i]);
        //                      ^                 ^
        //               先将上一次迭代结果插入    然后修改该结果,即逐一插入 S[i],如上图规律

这个思路是非常朴素的,上一道题其实也可以用这个思路来解,只不过上一道题里,二进制位的规律实在太明显,便会放弃这种类似穷举的方法。

但这道题里,我们在穷举的同时,也在排除重复项的干扰,却显得十分高效。

从 AC 后的效率图可以看出,这也是一个主流解法。