专题11 · 数据结构3
当"下标"不够用了：学号是字符串、编号到 20 亿、还要顺带排好序 ——
这就是 set 与 map 的主场。本讲吃透关联容器的有序性与 O(log n)，
并用两道真题把"去重排序"和"频次统计"彻底拿下。
关联容器全景（对应视频 43′42″）
🌳 set / multiset 0–15′
有序 + 去重（multiset 允许重复）。红黑树实现，双向迭代器。
解决：去重排序、前驱后继、存在性判断。
🔑 pair 与 map 15–30′
key → value 映射，key 唯一、自动按 key 升序。
解决：字符串/大编号当"下标"、频次统计。
⚡ unordered_map 30–43′
哈希表版 map：平均 O(1)，但不排序。
解决：只要计数、不需要顺序。
三种"数组下标用不了"的时刻
① 下标太大
要统计成分编号 2e9 的出现次数。
int cnt[2000000000] → 直接 MLE。
map<long long,int> cnt; cnt[x]++;
② 下标不是整数
要存"姓名 → 分数"。a["张三"] 数组做不到。
map<string,int> sc; sc["张三"]=95;
③ 还要顺带排好序
去重 + 升序输出。用数组要 sort + 手动去重两步。
set<int> s; 插完即为升序且无重复
set 的两大天性：去重 + 自动升序
逐个插入下面这串数，看 set 怎么"吞掉重复、排好顺序"。
insert 的返回值
pair<iterator,bool> r = s.insert(x);
r.second == true 表示新插入；false 表示已存在、没插进去。
这个 bool 经常用来判重。
set vs multiset
set：重复元素插不进去。
multiset：允许重复，s.count(x) 能拿到个数；
s.erase(x) 会删掉所有等于 x 的（要删一个得用迭代器）。
*it = 5 编译不过（改了会破坏有序性）。要改只能先删再插。在有序集合里"二分定位"
查一个数 x：lower_bound 找第一个 ≥ x，
upper_bound 找第一个 > x。看指针怎么跳。
怎么记这两个函数
把结果想成插入位置：
lower_bound(x) → 插在所有 < x 的后面（即第一个 ≥ x 处）；
upper_bound(x) → 插在所有 ≤ x 的后面（即第一个 > x 处）。
常用套路
① 判存在：s.find(x) != s.end()（或 s.count(x)）；
② 前驱：--s.lower_bound(x)；
③ 后继：s.upper_bound(x)；
④ 区间计数：distance(l, r)。
--s.begin() 是未定义行为：
求前驱前必须确认 lower_bound(x) != s.begin()，否则 x 比所有元素都小时会崩。map：把"名字"当下标用
姓名 → 分数。注意观察 用 [] 访问一个不存在的 key 会发生什么。
pair：两个值绑一起
pair<string,int> p("张三", 95); p.first; p.second; auto q = make_pair("李四", 88); // 比较：先比 first，相等再比 second
map 的每个元素就是一个 pair<key,value>。
遍历 map
for(auto& p : mp){ cout << p.first << " " << p.second << '\n'; }
按 key 升序自动排好（红黑树中序遍历）。
mp[key] 会把不存在的 key 插进去！
判断"某 key 是否存在"必须用 mp.find(key) != mp.end() 或 mp.count(key)，
不要用 mp[key] —— 它会悄悄插入一个值为 0 的元素，改变 mp.size()。O(n) 扫一遍 vs O(log n) 走树高
同一个"找不找得到"的问题，两种做法的比较次数差多少？
为什么是 log n（像查字典）
把 set 想成一本永远按页码排好序的书：翻到中间看一眼，就能排除掉一半，
再在剩下的一半里翻中间……n = 10 万时只要约 17 次就能找到。
对比：用数组一个个找，最坏要找 10 万次。
红黑树做了什么（了解即可）
它就是上面那本"会自动整理顺序的书"。插入删除后它会自己调整，保证查找一直很快。 调整的细节（变色、旋转）不需要你写，只要记住结论：它是平衡的，所以快。
insert / erase / find / count / lower_bound 都是 O(log n)；
begin() / rbegin()、size() / empty() 是 O(1)；
distance() 是 O(n)。去重 + 排序：set 一遍搞定
原始序列逐个进 set：重复的被吞掉，剩下的天然升序。
用 set 的解法
set<int> s; for(...) s.insert(x); cout << s.size() << '\n'; for(auto v : s) cout << v << ' ';
两行核心代码，去重排序一次完成。
不用 set 的解法
sort(a, a+n); int m = 0; for(int i=0;i<n;i++) if(i==0 || a[i]!=a[i-1]) b[m++] = a[i];
先排序，再用"和前一个不同"去重。
明明的随机数 · 完整代码
#include <iostream> #include <set> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; if(!(cin >> n)) return 0; set<int> s; // ★ 去重 + 升序 for(int i=0;i<n;i++){ int x; cin >> x; s.insert(x); // 重复自动忽略 } cout << s.size() << '\n'; // ★ 第一行：个数 for(set<int>::iterator it = s.begin(); it != s.end(); ++it){ // ★ 不能写 it < s.end() cout << *it << ' '; // 迭代器是"指针"，取值要 * } cout << '\n'; return 0; }
< / +n，只能用 != 和 ++。cout << it 会输出地址（或编译错误），
必须 *it。s[0] 编译不过 ——
set 没有 []，因为它不是随机访问。要第 k 小只能从头 advance。sort 版本也是 O(n log n)，但要多写 5 行。）频次统计：map 计数 vs 摩尔投票
同一个问题两种方法。先看 map 计数，再看 摩尔投票（两两抵消）。
map 计数（本讲主题）
每个成分记一个次数，最后找有没有 cnt > N/2。
优点：直观、还能顺便输出所有频次；代价：O(n log n) 时间、O(n) 空间。
摩尔投票（拓展）
把"当前候选"和"别的数"两两抵消，剩下的就是候选，最后数一遍验证。
优点：O(n) 时间、O(1) 空间；局限：只能找"超过一半"的。
主要成分 · 两种写法
// 方法一：map 计数（本讲主题） #include <map> map<long long, int> cnt; for(int i=0;i<n;i++){ long long x; cin >> x; cnt[x]++; // ★ 不存在就插入，初值 0 } int half = n / 2; // ★ N÷2 向下取整 for(auto& p : cnt){ if(p.second > half){ // ★ 严格大于 cout << p.first << '\n'; return 0; } } cout << "No\n";
// 方法二：摩尔投票（O(1) 空间） long long cand = 0; int c = 0; for(int i=0;i<n;i++){ long long x; cin >> x; a[i] = x; if(c == 0){ cand = x; c = 1; } else if(x == cand) c++; else c--; // 不同就抵消 } int tot = 0; // ★ 必须再数一遍验证 for(int i=0;i<n;i++) if(a[i]==cand) tot++; if(tot > n/2) cout << cand << '\n'; else cout << "No\n";
map 的 key 必须用 long long，用 int 会溢出；
② 条件是 > n/2（严格大于），写成 >= 在偶数 N 时会错；
③ 摩尔投票必须再数一遍验证 —— 抵消剩下的只是"候选"，不一定真超过一半。要"有序"还是要"更快"？
| 特性 | map（红黑树） | unordered_map（哈希表） |
|---|---|---|
| 查找/插入/删除 | O(log n)，稳定 | 平均 O(1)，最坏 O(n) |
| 是否按键排序 | ✅ 自动升序 | ❌ 无序 |
| 能否 lower_bound / 前驱后继 | ✅ 可以 | ❌ 不支持 |
| key 的要求 | 能比较（<） | 能哈希 + 判等 |
| 自定义类型 | 写比较函数 | 要写哈希函数（麻烦） |
什么时候必须用 map
① 要按 key 顺序输出（如统计后按数升序输出）；
② 要前驱 / 后继 / 区间（lower_bound）；
③ 数据卡哈希（担心被构造数据卡成 O(n)）。
什么时候用 unordered_map
① 只做计数、判重，完全不在乎顺序（如本题"主要成分"）；
② n 很大（1e6）且时间紧；
③ key 是整数 / string 这类有默认哈希的类型。
mp[key] 会插入不存在的 key。另外它没有 lower_bound，
凡是"要找第一个 ≥ x"的需求，只能回到 map。容器套容器：真题里常见的三种组合
① map + set
map<string, set<int>> mp; // 每个人 → 他做过的题号集合 mp["张三"].insert(1001);
用于"诗歌在线评测"类：按作者归档并自动去重排序。
② map 记最近位置
map<int, int> last; if(last.count(x)) ans = min(ans, i - last[x]); last[x] = i;
用于"最近的一对"：边扫边更新上次出现位置，一趟 O(n log n)。
③ 结构体入 set
struct Stu{ int id; string name; }; struct Cmp{ bool operator()( const Stu& a, const Stu& b) const{ return a.id < b.id; // 按 id 排序 } }; set<Stu, Cmp> s;
自定义"什么叫小"，set 才知道怎么排。
关联容器的易错辨析
① 想判断 key 是否存在于 map 中，应该用？
② set 里的元素想改成一个新值，应该？
③ 需要"按 key 从小到大输出"，选？
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
明明的随机数 · RANDOM
第1档 · 2 分钟n == 1 → 输出 1 和它本身
第2档 · 8 分钟
排序 + 手动去重（相邻比较），n ≤ 10⁵ 稳过
第3档 · 10 分钟
只去重不排序（保持原顺序）→ 部分测试点只查去重
第4档 · 15 分钟set<int> 插入后直接遍历输出，天然去重 + 有序
主要成分 · MAINCOMP
第1档 · 2 分钟
只有一种元素 → 就是它
第2档 · 8 分钟
双重循环统计每种出现次数，n ≤ 10⁴ 稳过
第3档 · 10 分钟
元素值域很小（如 ≤ 1000）→ 用数组当桶计数
第4档 · 15 分钟map<T,int> 计数，扫一遍取最大
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。椰程信奥当堂测评
① 主要成分中，N = 6、某成分出现 3 次，算不算主要成分？
② 明明的随机数里，set 遍历输出时要用什么比较迭代器？
③ 值域到 2×10⁹ 的编号要做频次统计，key 的类型应该是？
① key 是小连续整数吗？是 → 数组（最快）； ② 需要有序 / 前驱后继吗？需要 → map / set； ③ 只计数不在乎顺序吗？是 → unordered_map。 另外记住一条铁律：判存在用 find / count，绝不用 []。💡