复旦这道“集合交并”AcWing 3688在考研机试圈里很有名它表面上只是让你输出两个集合的交集和并集实际上却把 STL set 的常用操作、容器特性、边界处理全部串起来了。我在带学生刷题时发现很多人不是不会数学上的“交集并集”而是不知道在考场上怎样用 set 把代码写得又快又稳或者干脆因为踩了细节而白白罚时。这篇文章就把这道题从题目背景、代码实现到常见坑点完整拆开讲一遍适合正在准备考研机试、准备校招机考或者刚接触 STL 容器想找实战例子的读者。1. 题目背景与考点分析1.1 复旦大学机试为什么爱考集合运算考研机试和 ACM 比赛不一样它不追求“偏题怪题”反而更看重你在有限时间内能不能写出结构清晰、行为正确的代码。复旦大学计算机类机试出现的“集合交并”就是这样一类题目听上去简单却足够考察你对容器和算法的熟练度。这类题目的输入往往是一组整数集合输出两个集合的交集和并集。第一眼看上去最朴素的做法是两层循环外层遍历第一个集合内层遍历第二个集合判断元素是否相同。如果只是写“伪代码”这种做法没有任何问题。但放进机试环境里就有两个隐患一是时间复杂度不稳定二是重复元素、无序排列会让代码瞬间变得臃肿。用 STL set 之后输入时的自动去重和自动排序直接帮你把“元素是否出现过”和“输出顺序”这两个麻烦解决了。我个人的理解是这道题的核心并不是考验“会不会求交集并集”而是考验你有没有养成“模拟前先想容器”的思维习惯。机试里大部分题给的数据范围都没大到必须上复杂算法但如果你一上来就写一堆 for 循环后面再改数据结构的成本会很高。复旦机试这种“一道题里同时涉及并集和交集”的题型恰好倒逼你从 set、unordered_set、vector 等容器里做选择这个选择本身就是真正的得分点。1.2 考点拆解set 到底在考什么先明确一个事实STL set 是关联容器底层通常实现为红黑树它内部按照 key 值自动排序并且保证元素唯一。也就是说当你执行insert(x)时set 会自己判断 x 是否已经存在存在就不重复插入同时内部始终维持有序状态。这给“集合交并”题带来了三个直接好处。第一去重不用你管。如果题目输入里同一个元素出现多次set 天然只保留一份这样交集和并集的结果不会因为输入重复而输出多余数字。第二排序不用你管。输出要求如果写的是“从小到大”set 遍历出来的顺序天然就是升序不需要再调用 sort。第三查找效率有保证。单个元素的插入、删除、查找都是 O(log n)对机试常规数据规模来说这是个非常舒适的量级。另外还要注意 set 和 multiset 的区别。multiset 允许重复元素适合统计出现次数而这道题的“集合”概念明确要求去重所以用 set不要看到“集合”就顺手拿数组或者 multiset。很多人第一反应是把输入存进 vector然后 sort unique再用循环求交集并集。这当然也正确但代码长度和维护成本都比 set 版本高。机试现场能少写十行就少写十行。2. 解题思路与关键技术选型2.1 用 set 还是 unordered_set这是很多人在写这道题时会纠结的问题。unordered_set 底层是哈希表理论单次插入、查找平均 O(1)看起来比 set 的 O(log n) 更诱人。但在这道题里我建议优先选 set除非题目明确要求“只关心存在性、不要求顺序”。原因是输出格式。集合交并的输出一般都需要“从小到大逐个输出”中间用空格分隔。set 遍历是有序的直接正序遍历就能满足而 unordered_set 的存储顺序是哈希冲突后的结果往往杂乱无章。如果非要用 unordered_set你就得把所有元素倒进 vector 再排序排序复杂度同样是 O(n log n)反而把优势丢了。还有一点是考试心态。用 set 写代码时insert、find、count这几个接口都非常直观不容易写出内存越界问题。unordered_set 虽然接口类似但遇到需要“按顺序输出”的题目容易下意识写错遍历逻辑。机试不是比拼极限性能而是比拼一次写对的概率。所以在集合交并题里set 是性价比最高的选型。如果需要处理的数据量特别大比如元素数量在百万级别set 的 log 因子可能会比较紧张。这时可以改用 unordered_set 存集合同时用一个额外 vector 记录元素用于最后排序。不过考研机试通常不会在这个数据范围上卡常数我建议先写 set 版本等真超时了再去优化。实际考场上大多数人超时不是因为 set而是因为代码逻辑有问题。2.2 并集与交集的核心写法先说并集。并集的数学定义是“两个集合所有元素合在一起”放到 set 里就是把第一个集合的元素插入结果 set再把第二个集合的元素也插入结果 set。因为 set 自动去重重复插入不会产生任何副作用最终剩下的一定是两个集合的全集。伪代码思路setint result a; // 先把第一个集合复制进去 for (auto x : b) { result.insert(x); // 插入第二个集合重复部分自动忽略 }用for (auto x : b)遍历 set 时x 是集合中的元素值不是迭代器直接 insert 即可。这是 C11 引入的范围 for 循环在机试环境里推荐使用比手动写迭代器要安全得多。交集则有两个方向。第一种是遍历较短的集合对每个元素检查是否也出现在另一个集合里setint res; if (a.size() b.size()) { for (auto x : a) { if (b.count(x)) res.insert(x); } } else { for (auto x : b) { if (a.count(x)) res.insert(x); } }第二种是用 STL 算法set_intersection。如果使用了#include algorithm可以直接setint res; set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(res, res.begin()));很多初学者用不惯inserter老觉得迭代器参数很绕于是干脆放弃这个算法。其实理解思路很简单set_intersection会把结果元素写到第五个参数指向的位置而 set 不能通过*it value来赋值所以必须用inserter这种“插入型迭代器”。要是你对这条不熟老老实实写第一种手动遍历也是完全正确的而且更不容易出错。3. 完整代码实现与逐段拆解3.1 一个可复现的完整解法我按考研机试常见的输入习惯给出一个版本第一行输入两个整数 n、m分别表示两个集合的元素个数第二行输入 n 个整数第三行输入 m 个整数。程序对所有测试数据循环处理直到文件结束。#include bits/stdc.h using namespace std; int main() { int n, m; while (cin n m) { setint a, b; for (int i 0; i n; i) { int x; cin x; a.insert(x); } for (int i 0; i m; i) { int x; cin x; b.insert(x); } setint inter, uni; // 交集遍历较小的集合用 count 判断是否存在 if (a.size() b.size()) { for (auto x : a) { if (b.count(x)) inter.insert(x); } } else { for (auto x : b) { if (a.count(x)) inter.insert(x); } } // 并集先把 a 全部放进去再把 b 放进去 uni a; for (auto x : b) uni.insert(x); // 输出交集 bool first true; for (auto x : inter) { if (!first) cout ; cout x; first false; } cout \n; // 输出并集 first true; for (auto x : uni) { if (!first) cout ; cout x; first false; } cout \n; } return 0; }上面的代码中while (cin n m)是一个很经典的机试写法。如果题目是单组测试输入完 n、m 和元素后循环自然结束进入下一次输入时会到达 EOF循环结束不会多输出任何空结果。如果题目是多组测试这也能顺利处理。注意输出格式我使用了bool first来控制空格而不是在每个元素后面都输出一个空格再输出换行。这也是一个细节。很多人喜欢写成cout x 最后再cout endl看起来没问题但评测机通常要求“每行末尾不能有多余空格”虽然很多题的评测系统会忽略但野外机试有的不会。所以老老实实用 first 变量控制能省很多不必要的心跳。3.2 三个最容易被细节坑到的地方第一个坑千万不要在输入时假设“第一个集合一定没有重复元素”。题面说集合元素必然不重复但实际输入文件里出题人可能故意插入重复数据来考验去重能力。用 set 就无所谓了insert 会判断。如果用了 vector 并且没 unique最后交集并集会输出重复数字。第二个坑输出顺序。并集结果的顺序不是“随机的”而是 set 内部红黑树的升序。你用 set 就不用关心排序。但如果有人在求交集时用vector加find最后可能会忽略排序直接输出原始顺序这种解法就算交出来结果也可能和标准答案不一致因为标准输出强制要求升序。第三个坑空集合的输出。理论上如果两个集合没有交集交集结果就是一个空行。如果用普通的循环输出空集合就是什么都不输出但换行符输出不输出不同题目要求不一样。我给出的上面代码中空交集也会输出一个\n这样保证格式稳定。如果你直接写for遍历交集然后输出空集就会导致连换行都没有两个输出粘在一起那就错了。4. 常见问题与调试排查实录4.1 为什么我不用 vector 排序去重有同学会问用 vector 存下来sort 一下再 unique也能得到有序且不重复的集合再双指针求交集并集不是更“基础”吗完全不推荐机试时这样做。首先vector sort unique 的代码量超过 set 版本双指针求交集还要单独写循环要考虑两个指针越界问题其次如果题目要求多组测试为了每一组都能复用容器你还要记得把 vector clear否则上一组的残留元素会污染下一组结果。用 set 的时候setint a, b;每组循环重新定义自动销毁释放不需要手动 clear代码逻辑会非常干净。而且 set 的count接口对“判断元素是否存在”这个语义太合适了。count对于 set 只会返回 0 或 1因为 set 不允许重复元素。读代码的人一眼就能看出你是在查存在性。但我也要补充一句如果题目数据量特别大比如 10 万级别的元素set 的 O(n log n) 完全可以接受如果到了 100 万还是用 unordered_set 加上 final sort 更安心。考研机试的集合题一般不会给到百万级所以按照常规做法来就好。4.2 边遍历边删除交集中的经典翻车有些同学想用“删减法”求交集先复制一份 set遍历另一个集合如果元素在结果集合中不存在就把它删掉。这个思路听起来有道理但实现时最容易撞上迭代器失效问题。比如下面这种写法setint inter a; for (auto it b.begin(); it ! b.end(); it) { if (!inter.count(*it)) inter.erase(*it); }问题在于inter.count(*it)是没问题的但如果改成更复杂的操作比如边遍历边判断边删除同一个容器的元素就容易把迭代器搞乱。set 的 erase 会导致指向被删除元素的迭代器失效如果后面的代码还继续使用就会未定义行为。更隐蔽的问题还有这种“从 a 中删除不在 b 中的元素”的方式如果 a 和 b 完全不同最后会把 a 删除到空集语义上没问题但如果 a 很大、b 很小复杂度是 a 的遍历加上 log 操作也还好。真正的问题是代码可读性差面试官或阅卷人很难一眼看出你的意图。所以机试没必要玩这种花活遍历较小集合用count筛选再插入到结果集就足够满分。4.3 编译环境与万能头文件AcWing 平台和大部分考研机试环境都支持#include bits/stdc.h。这个万能头文件在本地 G 环境通常也能编译但有些学校机房用的是较老的 Visual C可能不支持。如果你不确定考场环境尽量写#include iostream #include set #include algorithm using namespace std;代码只多了三行却避免了老编译器不支持万能头的风险。这道题不需要 vector只需要 iostream、set再加上 algorithm 以防要用set_intersection。我建议稳健地分开写头文件因为养成习惯后万一遇到环境不支持bits/stdc.h你也能立刻适应。还有一个容易忽视的点要留意 C 标准。AcWing 默认一般是 C11所以我的代码里用了for (auto x : a)没问题。如果有些老版本要求 C98得改成迭代器写法。在考试开始前 5 分钟先建个空程序编译一下测试auto和范围 for 是否支持。别等到交题时才发现编译不过。5. 从这道题延伸到机试常见变式5.1 差集、对称差与字符串集合把交并题扩展一下最常见的变式是求差集也就是“在 A 中但不在 B 中的元素”。用 set 写也非常简单setint diff; for (auto x : a) { if (!b.count(x)) diff.insert(x); }如果要对称差A 和 B 中只出现在一个集合中的元素可以先求并集再删除交集里的所有元素也可以分两步分别求 A-B 和 B-A再合并。这两种思路都能写但要注意遍历并集同时删除交集元素的迭代器问题。稳妥方案是分别生成两个差集然后再次插入到一个新的 set 里。还有的题目会把整数改成字符串比如“给定两个包含人名的集合输出交集”。这种题的核心代码完全一样只需要把setint改成setstring。C 的 set 对 string 已经做过操作符重载按字典序排序。如果你用 C 风格字符串数组反而要去写 strcmp 和 strcpy容易出错。看到这类题时不要急着一行行读先判断元素类型再选容器这才是机试老手的第一反应。5.2 时间复杂度和空间复杂度的取舍我在辅导过程中经常强调一句话机试不只看你会不会还要看你贪不贪。所谓贪就是总想用最简单的暴力去解决一切问题。但暴力并不意味着“低效大循环”而是“代码思路明确、实现足够短”。set 版本的时间复杂度主要来自两组输入共 nm 次插入操作每次 O(log n)求交集最多遍历较小组大小每次 count O(log n)求并集遍历另一组大小每次 insert O(log n)。整体大约是 O((nm)log(nm))。换成 vector sort整体是 O(n log n m log m n m)看起来好像更优一些尤其当 n、m 都很大时常数也不差。但题目的输出和去重逻辑都要自己维护代码容易出错。对考研机试而言代码正确率的重要性远大于那一点点常数差异。真正遇到需要压榨常数时你不会用 set 做百万元素你会换 unordered_set。你需要注意的是不要在写题过程中反复换方案这会浪费大量考试时间。5.3 机试中如何用五分钟稳定过题如果你看过我的其他解题笔记会发现我特别强调“先看数据范围再想容器再写输出格式”。这道题的数据范围一般在几百到几万所以直接 set 起步。流程可以固定成四步。第一步读入 n 和 m定义好 set。第二步一边读一边 insert不存在“先存数组再去重”这种多余的中间步骤。第三步分别求交并交集先遍历小集合并集直接合并。第四步用 first 变量控制空格输出。这套流程前前后后不会超过五分钟。当你把 set 用顺手之后再看其他类似题目比如统计不同数字个数、求公共元素、合并去重排序思路都是一通百通。我个人在实际刷题时的一个感受是看到“集合”这两个字先别急着套数学课上学的“交集是阴影重叠部分”而是要想清楚输出要求。输出要求决定容器选择。若要求升序就上 set若只要求存在性不要求顺序才轮到 unordered_set若还要求元素可重复就要 multiset 或者 map 计数。这样一种思维链才是做这题最大的收获。6. 总结之外的几句大实话如果非要给这道题一个定位它是 STL 容器入门后最好的“整合练习题”。在写代码的时候你会发现真正难的不是 set 本身而是遍历和删除、空集和空格、多组输入和 EOF这些边角细节恰恰是机试经常扣分的地方。我在实际教学中常让学员把 vector、set、unordered_set 三个版本都写一遍互相比较代码长度和心态压力。大多数人在写过 set 版本之后都会感叹“早知道用 set 我就不用纠结了”。这份“早知道”其实就是刷题经验的一部分。最后分享一个小技巧调试时如果发现输出多了或者少了空格可以先打印出 set 的大小确认输入是否完整如果发现交集为空但自己总觉得应该不为空检查一下是不是在求交集之前把其中一个 set 误改了。C 的 set 赋值默认是深拷贝uni a之后就不会和 a 互相牵连这点和数组名不一样可以放心用。不过也别把引用和赋值搞混否则排错会非常痛苦。保持代码结构简单考场上才能稳定发挥。