01先把问题说具体
给两组报名名单,怎样找共同成员,并保留第一组名单的首次出现顺序?
02一步步得到方法
集合首先是一种语义
集合只关心某个元素是否存在,不记录重复次数。列表 [2,2,3] 转成集合得到 {2,3},这不是排序,也不是计数。需要次数时用哈希表;需要顺序时要额外保存顺序。
哈希集合用哈希值定位候选桶,再用相等判断确认元素。哈希相同不代表元素相等。键必须遵守相等对象具有相同哈希的约定,且存入后影响相等与哈希的内容不能随意改变。
从双重循环推到成员判断
对 a 中每个元素扫描 b,会重复寻找同一批值。先将 b 放入集合,将一次线性扫描的结果保存成可复用索引;再扫描 a,每次做平均常数时间的成员检查。
若 a 自身有重复,还需 emitted 集合。只有既属于 b 又没输出过的值才进入答案。这样集合负责判断,列表负责保留顺序,两种结构各做擅长的事。
不要混淆哈希集合与有序集合
哈希集合通常不承诺按数值排序;平衡树集合可提供有序遍历和前驱后继,但操作常为 O(log n)。选择结构时先看需要的操作,不要只看名字里都有集合。
03把一个小例子完全算清楚
a=[3,1,3,2],b=[2,3,4],求保序交集。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 准备 | allowed={2,3,4},emitted={} | 先建立 b 的成员索引 |
| 读取 3 | 答案 [3] | 存在且未输出 |
| 读取 1、3 | 答案仍 [3] | 1 不在 b;第二个 3 已输出 |
| 读取 2 | 答案 [3,2] | 存在且未输出 |
窄屏可左右滑动表格,阅读完整计算与理由。
交集成员为 2、3;接口要求保留 a 的首次出现顺序,因此返回 [3,2]。
04为什么这个方法成立
- 每个输出元素同时来自 a 和 b,保证没有多余成员。
- 扫描 a 的所有位置,首次遇到任一共同元素都会输出,保证没有遗漏。
- emitted 阻止重复,顺序扫描保证结果按首次出现顺序排列。
05把推导翻译成代码
Python · 可独立运行的教学实现
def ordered_intersection(a, b):
allowed = set(b)
emitted = set()
result = []
for x in a:
if x in allowed and x not in emitted:
result.append(x)
emitted.add(x)
return result逐个理解关键决定
allowed = set(b)- 预处理 b,代价不是零;处理多次查询时这笔成本可以复用。
x not in emitted- 成员判断与去重是两个不同条件。
result.append(x)- 输出顺序来自扫描 a,而非遍历 set。
06时间、空间与实现范围
哈希操作平均 O(1) 时,总时间 O(n+m),额外集合和输出空间 O(n+m) 上界。
极端哈希冲突会恶化性能;键很长时,哈希与比较的成本也需计入。
07改变条件,检查哪里会出错
把 set 当成有序去重列表
显式维护结果列表,或在题意要求数值顺序时对结果排序。
用集合统计频次
集合会丢掉重复次数,改用字典或 Counter。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
a=[1,1],b=[1,1,1],本课输出什么?
需要一点提示
接口求集合交集。
查看解析与答案
[1]。若要求多重集合交集,应输出两次 1,需用频次数量取最小值。
如何求差集 a−b 并保序去重?
需要一点提示
只改成员条件。
查看解析与答案
将 x in allowed 改为 x not in allowed,保留 emitted 与结果列表。
查询一次且 b 只有两个元素,还值得建集合吗?
需要一点提示
渐近分析之外还有什么?
查看解析与答案
未必。直接比较两个值可能更简单、常数更小;大量重复查询时索引收益更明显。