专题进阶 · 基础与数据结构推荐总顺序 · 第 27 / 148 课

把集合操作转成成员判断,并解释去重、交并差与哈希前提。

先学会这些,再进入本课 哈希表 字符串
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 基础与数据结构

集合Set

表达成员关系和去重;哈希集合与有序集合有不同的复杂度保证。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

把集合操作转成成员判断,并解释去重、交并差与哈希前提。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 每个输出元素同时来自 a 和 b,保证没有多余成员。
  2. 扫描 a 的所有位置,首次遇到任一共同元素都会输出,保证没有遗漏。
  3. 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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

a=[1,1],b=[1,1,1],本课输出什么?

需要一点提示

接口求集合交集。

查看解析与答案

[1]。若要求多重集合交集,应输出两次 1,需用频次数量取最小值。

练习 2 · 边界与辨析

如何求差集 a−b 并保序去重?

需要一点提示

只改成员条件。

查看解析与答案

将 x in allowed 改为 x not in allowed,保留 emitted 与结果列表。

练习 3 · 变式与迁移

查询一次且 b 只有两个元素,还值得建集合吗?

需要一点提示

渐近分析之外还有什么?

查看解析与答案

未必。直接比较两个值可能更简单、常数更小;大量重复查询时索引收益更明显。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Python 官方教程 · 数据结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。