【STL】有序容器的集合操作

摘要: STL 中的有序容器的集合操作

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

std::algorithm 中有一组针对有序容器的集合操作，总览如下：

• 子集：includes
• 交集set_intersection
• 并集set_union
• 差集set_difference
• 对称差集set_symmetric_difference

本文首先介绍有序容器的这些集合操作，然后解决力扣的两个题目，其中第 350 使用了交集、1452 题使用了子集。

• 交: 350. 两个数组的交集 II
• 子集: 1452. 收藏清单

---

有序容器的集合操作

STL 算法分为几大类，例如很多算法都可以归为非修改性序列算法和修改性序列算法。其中一大类是与排序相关的，具体包括排序本身的算法和针对已排序序列的算法。

对于排序本身的算法，有排序：sort,stable_sort, partial_sort, partial_sort_copy；划分：partition, stable_partition；第 n 大：nth_element。

对于针对已排序序列的算法，有二分：binary_search, equal_range, lower_bound, upper_bound；归并：merge, inplace_merge，除此之外，还有集合运算

一个序列可以看作是集合，STL 针对这种视为集合的有序序列，提供了集合运算算法，例如交集，并集等。但是应用这些算法的序列必须是有序的，否则这种运算机器低效，甚至结果序列不一定符合集合论规则。

这些集合运算对 set 和 multiset 也能很好地工作，因为这些容器也是有序的。

子集 includes

template<class In1, class In2>
bool includes(In1 first1, In1 last1, In2 first2, In2 last2);
template<class In1, class In2, class Cmp>
bool includes(In1 first1, In1 last1, In2 first2, In2 last2, Cmp cmp);

检测第二个序列 [first2, last2)] 的所有元素是否都是第一个序列 [first1, last1)] 的元素，即第二个序列是否是第一个序列的子集。

交集 set_intersection

template<class In1, class In2, class Out>
Out set_intersection(In1 first1, In1 last1, In2 first2, In2 last2, Out res);
template<class In1, class In2, class Out, class Cmp>
Out set_intersection(In1 first1, In1 last1, In2 first2, In2 last2, Out res, Cmp cmp);

以排序序列的方式产生输出，输出的序列是两个序列的交集。

并集 set_union

template<class In1, class In2, class Out>
Out set_union(In1 first1, In1 last1, In2 first2, In2 last2, Out res);
template<class In1, class In2, class Out, class Cmp>
Out set_union(In1 first1, In1 last1, In2 first2, In2 last2, Out res, Cmp cmp);

以排序序列的方式产生输出，输出的序列是两个序列的并集。

差集 set_difference

template<class In1, class In2, class Out>
Out set_difference(In1 first1, In1 last1, In2 first2, In2 last2, Out res);
template<class In1, class In2, class Out, class Cmp>
Out set_difference(In1 first1, In1 last1, In2 first2, In2 last2, Out res, Cmp cmp);

产生一个序列，其元素属于第一个序列，但不属于第二个序列。

差集 set_symmetric_difference

template<class In1, class In2, class Out>
Out set_symmetric_difference(In1 first1, In1 last1, In2 first2, In2 last2, Out res);
template<class In1, class In2, class Out, class Cmp>
Out set_symmetric_difference(In1 first1, In1 last1, In2 first2, In2 last2, Out res, Cmp cmp);

产生一个序列，其元素属于两个序列之一，但不同时属于二个序列。

以上五个集合运算，后四个运算的接口除了函数名以外完全一样。

例题

交集: 350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

进阶：

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小，哪种方法更优？
• 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

算法

交集的问题有两种主流做法，一种是基于哈希表，需要 $O(N)$ 时间 $O(N)$ 空间，另一种基于排序和双指针，需要 $O(N\log N)$ 时间但是空间为 O(1)。如果数组有序，则直接用双指针就可以有 $O(\log N)$ 时间，数组有序也是使用 STL 序列的交集算法的条件。

除此之外，基于排序的方法，有一种常见的 Follow up 问题，即当数据在磁盘上时且量极大，无法加载所有数据的情况，如何解决。因空间不够，就只能用排序+双指针的做法，双指针的过程没有什么变化(用 STL 函数也一样)，而排序过程又有以减少 IO 次数的各种优化，这是另一个话题了。这里关注如果用 STL 算法如何写。

要用 STL 算法实现交集，也是要排序的，只是排好序后，将双指针算法改成调用 set_intersection 函数。

set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), insert_iterator<vector<int>>(result, result.begin()));

注意第五个参数 insert_iterator<vector<int>>(result, result.begin() 是插入迭代器。

代码 (C++)

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.empty() || nums2.empty())
            return vector<int>();
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int n1 = nums1.size(), n2 = nums2.size();
        vector<int> result;
        set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), insert_iterator<vector<int>>(result, result.begin()));
        return result;
    }
};

子集: 1452. 收藏清单

给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。

请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。

提示：
1 <= favoriteCompanies.length <= 100
1 <= favoriteCompanies[i].length <= 500
1 <= favoriteCompanies[i][j].length <= 20
favoriteCompanies[i] 中的所有字符串 各不相同 。
用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单， favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
所有字符串仅包含小写英文字母。

示例 1：
输入：favoriteCompanies = [[“leetcode”,”google”,”facebook”],[“google”,”microsoft”],[“google”,”facebook”],[“google”],[“amazon”]]
输出：[0,1,4]
解释：
favoriteCompanies[2]=[“google”,”facebook”] 是 favoriteCompanies[0]=[“leetcode”,”google”,”facebook”] 的子集。
favoriteCompanies[3]=[“google”] 是 favoriteCompanies[0]=[“leetcode”,”google”,”facebook”] 和 favoriteCompanies[1]=[“google”,”microsoft”] 的子集。
其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。

示例 2：
输入：favoriteCompanies = [[“leetcode”,”google”,”facebook”],[“leetcode”,”amazon”],[“facebook”,”google”]]
输出：[0,1]
解释：favoriteCompanies[2]=[“facebook”,”google”] 是 favoriteCompanies[0]=[“leetcode”,”google”,”facebook”] 的子集，因此，答案为 [0,1] 。

示例 3：
输入：favoriteCompanies = [[“leetcode”],[“google”],[“facebook”],[“amazon”]]
输出：[0,1,2,3]

算法

本题是比较直接的子集判断，没举每一对人，判断两个人的清单是否有子集关系。

先将所有人的清单排序，再对每一对人的清单 item1 和 item2(item1 元素个数多于 item2) 调用以下判断。

if(includes(item1.begin(), item1.end(), item2.begin(), item2.end()))

若判断为真，则 item2 是 item1 的子集。

代码 (C++)

class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        int n = favoriteCompanies.size();
        vector<bool> flags(n, true);
        for(vector<string>& item: favoriteCompanies)
            sort(item.begin(), item.end());
        for(int i = 0; i < n; ++i)
        {
            const vector<string> &item1 = favoriteCompanies[i];
            for(int j = 0; j < i; ++j)
            {
                if(flags[j])
                {
                    const vector<string> &item2 = favoriteCompanies[j];
                    if(item1.size() > item2.size())
                    {
                        // item1 比较长
                        if(includes(item1.begin(), item1.end(), item2.begin(), item2.end()))
                            flags[j] = false;
                    }
                    else
                    {
                        // item2 比较长
                        if(includes(item2.begin(), item2.end(), item1.begin(), item1.end()))
                        {
                            flags[i] = false;
                            break;
                        }
                    }
                }
            }
        }
        vector<int> result;
        for(int i = 0; i < n; ++i)
            if(flags[i])
                result.push_back(i);
        return result;
    }
};

---