CC++ & Algorithm

集合算法：set_union、set_intersection与set_difference

极难3
语言版本：通用
概述：学会对有序区间进行集合运算，包括并集、交集和差集，就像数学课上学的韦恩图。

学会用代码做集合运算：并集、交集和差集

你有没有遇到过这样的问题：

  • 你们班有30个人，其中15人参加了数学兴趣小组，18人参加了英语角，有8人两个都参加了。那么只参加数学的有几人？至少参加一个的有几人？
  • 你的零花钱账单里，买零食花了20元，买文具花了15元，那么既买零食又买文具的东西有哪些？

这些其实就是数学里的集合运算。在编程里，我们可以用C++的STL算法库，对已经排好序的数据快速做并集、交集、差集。就像画韦恩图一样简单，但比手算快得多！

集合算法是干什么的？

简单说，就是给你两个“有序列表”，然后：

  • 并集（union）：把两边所有不重复的元素合在一起。
  • 交集（intersection）：找出两边都有的元素。
  • 差集（difference）：找出只在第一个列表里，不在第二个里的元素。
  • 对称差集（symmetric_difference）：找出两个列表里“独有”的元素（就是并集减去交集）。

这些算法都要求输入数据是按从小到大排好序的（默认用<比较），这样它们才能用两个“指针”同时扫描，效率很高（O(m+n)）。

四个集合算法的详细讲解

1. set_union —— 并集

生活例子：你爸爸给了你100元零花钱，妈妈给了你50元。他们给的钱可能有重叠（比如都给了买书的钱）。并集就是总共可以花的钱（每个项目只算一次）。

C++用法：

#include <vector>
#include <algorithm>
#include <iterator>  // back_inserter

vector<int> set1 = {1, 2, 3, 4, 5};    // 父亲给的金额
vector<int> set2 = {4, 5, 6, 7, 8};    // 母亲给的金额
vector<int> result;                     // 合并结果
set_union(set1.begin(), set1.end(),      // 第一个区间
          set2.begin(), set2.end(),      // 第二个区间
          back_inserter(result));        // 输出到result末尾
// result = {1,2,3,4,5,6,7,8}  注意4和5只出现一次

算法怎么工作？
想象两个人各拿一个指针，从最左边开始。比谁指向的数字小，小的就输出，然后指针往前移。如果一样大，就输出一个，两个指针同时往前移。这样就保证输出有序且不重复。

注意：如果原数组里本身有重复元素，比如{1, 2, 2, 3}和{2, 2, 4}，并集会输出两个中较大的出现次数。即{1, 2, 2, 3, 4}（2出现2次，因为第一个有2个，第二个有2个，取最大值2）。这不同于数学上的集合，但算法就是这么设计的。

2. set_intersection —— 交集

生活例子：你和好朋友都喜欢打篮球和玩游戏。交集就是你们都喜欢的活动。

C++用法：

vector<int> result;
set_intersection(set1.begin(), set1.end(),
                 set2.begin(), set2.end(),
                 back_inserter(result));
// result = {4, 5}   同时出现在两个数组中的数字

算法原理：两个指针同时移动，如果指向的数相等，就输出一次，然后都往后移。如果不等，则较小的那个指针往前走，继续比较。

常见坑：如果两个数组里同一个数出现多次，交集会输出出现次数较少的那一侧的次数。比如{1,1,2}和{1,2,2}，交集输出{1, 2}（1出现1次，2出现1次）。这和数学上取公共元素一次不同，但STL就是这么规定的。

3. set_difference —— 差集（前减后）

生活例子：你爸说“今天只能做三件事：写作业、练琴、跳绳”，你妈又说“必须做的事是练琴和阅读”。差集（爸爸的减去妈妈的）就是只出现在爸爸清单里的事：写作业和跳绳。

C++用法：

vector<int> result;
set_difference(set1.begin(), set1.end(),   // 第一个区间（被减数）
               set2.begin(), set2.end(),   // 第二个区间（减数）
               back_inserter(result));
// result = {1,2,3}   从set1中去掉set2里有的数

算法原理：比较两个指针，如果第一个的数小于第二个，说明这个数只在第一个里，输出它并移动第一个指针；如果相等，说明在第二个里也有，跳过（不输出），两个指针都移；如果第一个的数大于第二个，说明这个数不在第一个里（在第二个里），只移第二个指针。

注意顺序：set_difference(set1, set2) 和 set_difference(set2, set1) 结果不同。前者是 set1 独有的，后者是 set2 独有的。

4. set_symmetric_difference —— 对称差集

生活例子：你和朋友各自喜欢吃的东西，只属于一个人的美食（你们没有共同爱好的食物）。

C++用法：

vector<int> result;
set_symmetric_difference(set1.begin(), set1.end(),
                         set2.begin(), set2.end(),
                         back_inserter(result));
// result = {1,2,3,6,7,8}   只在set1或只在set2的数

算法原理：相当于两个差集的并集（(set1-set2) ∪ (set2-set1)）。算法会同时比较，哪个数只出现一次就输出。

新手最容易犯的错误 ❌

  1. 忘记排序：集合算法要求输入必须是有序的（默认升序）。如果你用的是乱序的 vector，结果会完全错误，而且不会报错！
    ✅ 解决方法：在使用算法之前，先对两个区间 sort()。

  2. 输出容器没有空间：很多人写 set_union(..., result.begin()) 但 result 是空的，这样会访问越界。
    ✅ 正确做法：使用 back_inserter(result) 自动扩展，或者先 result.resize(需要的最大大小)。

  3. 比较函数不一致：如果排序用的是 greater<int>()（降序），那么集合算法也必须用同样的比较函数作为第五个参数。
    ✅ 记住：排序和集合运算要用同一个比较器。

  4. 混淆差集顺序：set_difference(A, B) 和 set_difference(B, A) 结果不同，注意谁减谁。

  5. 分不清数学集合和STL集合：数学集合元素互异，STL算法允许重复，输出规则是按“计数”的。如果要求数学上的无重复集合，可以先对容器去重（unique）再运算。

完整可运行示例（贴近生活）

场景：班里统计同学们喜欢的水果。

  • 喜欢苹果的有：小明、小红、小刚、小丽、小华（用编号1~5表示）
  • 喜欢香蕉的有：小刚、小丽、小强、小美、小亮（编号3,4,6,7,8）
  • 注意：小刚和小丽两个都喜欢。

现在要求：

  • ① 至少喜欢一种水果的同学（并集）
  • ② 两种都喜欢（交集）
  • ③ 只喜欢苹果的（差集）
  • ④ 只喜欢其中一种的（对称差集）
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>  // back_inserter, ostream_iterator

using namespace std;

// 打印向量函数
void print(const string& msg, const vector<int>& v) {
    cout << msg;
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {
    // 喜欢苹果的同学编号（已排序）
    vector<int> apple = {1, 2, 3, 4, 5};  // 小明,小红,小刚,小丽,小华
    // 喜欢香蕉的同学编号（已排序）
    vector<int> banana = {3, 4, 6, 7, 8}; // 小刚,小丽,小强,小美,小亮

    print("喜欢苹果: ", apple);
    print("喜欢香蕉: ", banana);

    // 1. 并集：至少喜欢一种
    vector<int> union_result;  // 保存并集
    set_union(apple.begin(), apple.end(),
              banana.begin(), banana.end(),
              back_inserter(union_result));
    print("至少喜欢一种(并集): ", union_result);

    // 2. 交集：两种都喜欢
    vector<int> inter_result;  // 保存交集
    set_intersection(apple.begin(), apple.end(),
                     banana.begin(), banana.end(),
                     back_inserter(inter_result));
    print("两种都喜欢(交集): ", inter_result);

    // 3. 差集：只喜欢苹果
    vector<int> diff_apple_result;  // 保存差集（苹果 - 香蕉）
    set_difference(apple.begin(), apple.end(),
                   banana.begin(), banana.end(),
                   back_inserter(diff_apple_result));
    print("只喜欢苹果: ", diff_apple_result);

    // 4. 差集：只喜欢香蕉
    vector<int> diff_banana_result;  // 保存差集（香蕉 - 苹果）
    set_difference(banana.begin(), banana.end(),
                   apple.begin(), apple.end(),
                   back_inserter(diff_banana_result));
    print("只喜欢香蕉: ", diff_banana_result);

    // 5. 对称差集：只喜欢一种水果
    vector<int> symdiff_result;  // 保存对称差集
    set_symmetric_difference(apple.begin(), apple.end(),
                             banana.begin(), banana.end(),
                             back_inserter(symdiff_result));
    print("只喜欢一种(对称差): ", symdiff_result);

    return 0;
}

输出结果：

喜欢苹果: 1 2 3 4 5 
喜欢香蕉: 3 4 6 7 8 
至少喜欢一种(并集): 1 2 3 4 5 6 7 8 
两种都喜欢(交集): 3 4 
只喜欢苹果: 1 2 5 
只喜欢香蕉: 6 7 8 
只喜欢一种(对称差): 1 2 5 6 7 8

Python 中的对应操作（简单对比）

Python 的 set 类型本身就支持集合运算，而且不用提前排序，用起来非常方便。

apple = {1, 2, 3, 4, 5}     # 喜欢苹果的同学
banana = {3, 4, 6, 7, 8}    # 喜欢香蕉的同学

print("并集:", apple | banana)          # 或 apple.union(banana)
print("交集:", apple & banana)          # 或 apple.intersection(banana)
print("苹果独有:", apple - banana)      # 差集
print("香蕉独有:", banana - apple)      # 反向差集
print("仅一种:", apple ^ banana)        # 对称差集

输出：

并集: {1, 2, 3, 4, 5, 6, 7, 8}
交集: {3, 4}
苹果独有: {1, 2, 5}
香蕉独有: {8, 6, 7}
仅一种: {1, 2, 5, 6, 7, 8}

注意：Python 的 set 会自动去重，如果列表里有重复，需要先用 set() 转换。但如果想保留重复计数（如两个列表都有多个相同元素），就要用 collections.Counter，比如之前文末的例子。

跟我学：更多实用场景

  • 合并两门课程的成绩名单：一个90分以上的，一个85分以上的，求重叠部分（交集）。
  • 统计游戏道具：背包里有拾取过的道具列表，和通关奖励道具列表，求你能获得的新道具（差集）。
  • 比较两个购物清单：求出你妈让你买和你爸让你买的物品差异（对称差集）。

相关知识点指引

学完集合算法，你还可以了解：

  • sort() 排序函数 —— 因为集合算法必须基于有序数据。
  • unique() 去重算法 —— 如果你想要数学上无重复的集合，可以先排序再用unique。
  • merge() 合并两个有序区间 —— 和set_union类似，但不做去重，会把所有元素（包括重复）合并。
  • includes() 判断一个区间是否包含另一个区间。
  • set 容器 —— C++标准库中自带的有序集合容器，它内部就是红黑树，插入后自动排序，可以直接拿它的迭代器用集合算法。

掌握了这些，你就能像数学老师一样，轻松处理各种数据集合啦！

例题精讲

1单选题

给定两个已排序的整数区间 [1,2,3,4] 和 [3,4,5,6]，使用 std::set_union 求并集，输出区间为 [1,2,3,4,5,6]。以下关于该算法行为的描述正确的是？

A当两个区间存在重复元素时，set_union 会保留所有重复元素
B当两个区间存在重复元素时，set_union 只保留每个值的一个副本
Cset_union 要求输入区间必须严格递增（无重复元素）才能正确工作
Dset_union 的输出结果顺序是不确定的，依赖于具体实现
2单选题

执行以下代码后，result 向量中的元素是？ #include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> a = {1,2,3,5,7}; std::vector<int> b = {2,4,6,8}; std::vector<int> result(10); auto it = std::set_difference(a.begin(), a.end(), b.begin(), b.end(), result.begin()); result.resize(it - result.begin()); for(int x : result) std::cout << x << ' '; }

A1 2 3 5 7
B1 3 5 7
C2 4 6 8
D1 2 4 5 7
3判断题

使用 set_intersection 求两个有序向量的交集时，如果输入区间中存在重复元素，则输出区间中对应元素出现的次数等于两个输入区间中该元素出现次数的较小值。

4填空题
补全以下代码，使用 set_union 将两个已排序的向量 vec1 和 vec2 合并并去重，结果存入 result 中，result 初始为空。

#include <algorithm>
#include <vector>

std::vector<int> union_sorted(const std::vector<int>& vec1, const std::vector<int>& vec2) {
    std::vector<int> result;
    result.resize(vec1.size() + vec2.size()); // 先分配最大可能空间
    auto it = ___;
    result.resize(it - result.begin()); // 精确大小
    return result;
}
5填空题
补全以下代码，使用 set_intersection 找出两个有序数组（普通数组）中的交集元素，并输出到另一个数组 inter 中，假设 inter 大小足够。

#include <algorithm>
#include <iostream>

int main() {
    int a[] = {1,2,2,3,4};
    int b[] = {2,2,3,5};
    int inter[10];
    auto end = ___;
    for (auto p = inter; p != end; ++p) {
        std::cout << *p << ' ';
    }
    // 输出应为：2 2 3
}