小明的数字
活动安排
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
扑克牌
A-B数对
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
数值统计 【模版题】
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
快速拆步
ST表
二维前缀和
邻接表
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SET
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
离散化
随机化哈希
C++ 计数、哈希与集合类容器
一、计数数组
1. 作用
当数据的值域较小时，可以直接把“数值”当作数组下标，用数组记录出现次数。
例如：
若输入：
则：
2. 常见用途
用途 写法 统计 xxx 出现次数 cnt[x]++ 判断 xxx 是否出现 cnt[x] > 0 删除一个 xxx cnt[x]-- 枚举所有出现过的数 for(int i=0;i<=V;i++) if(cnt[i]) ... 求不同数字数量 第一次出现时令答案加 111
3. 特点
* 查询、修改复杂度：O(1)O(1)O(1)
* 速度非常快
* 需要值域不能太大
* 数组空间取决于“值域大小”，而不是实际出现多少种数字
例如 x≤109x\le 10^9x≤109 时，通常不能直接开：
此时可以考虑 map、unordered_map 或离散化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、MAP
1. 作用
map 用来维护：
例如统计数字出现次数：
可以理解为：
2. 特点
* Key 不需要连续
* Key 自动按照从小到大排列
* Key 不能重复
* 底层通常使用红黑树
* 插入、删除、查询复杂度均为 O(logn)O(\log n)O(logn)
3. 常用函数
写法 作用 mp[x] 访问 Key 为 x 的 Value；若不存在会自动创建 mp[x]++ 统计 x 的出现次数 mp.insert({x,y}) 插入 x -> y mp.find(x) 查找 Key x mp.count(x) 判断 Key x 是否存在 mp.erase(x) 删除 Key x mp.size() Key 的数量 mp.empty() 判断是否为空 mp.clear() 清空 mp.lower_bound(x) 第一个 Key ≥x\ge x≥x 的位置 mp.upper_bound(x) 第一个 Key >x>x>x 的位置
4. 遍历
遍历顺序按照 Key 从小到大。
5. 查找
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、UNORDERED_MAP
1. 作用
unordered_map 同样维护：
常见写法：
2. 特点
* 底层为哈希表
* 不维护 Key 的大小顺序
* 平均插入、查询、删除为 O(1)O(1)O(1)
* 最坏情况下可能退化到 O(n)O(n)O(n)
* 适合值域很大，只需要快速查询、计数，不需要有序性的情况
3. 常用函数
写法 作用 mp[x] 访问 Key 为 x 的 Value mp[x]++ 统计次数 mp.insert({x,y}) 插入 mp.find(x) 查找 mp.count(x) 判断是否存在 mp.erase(x) 删除 mp.size() 元素数量 mp.empty() 判断是否为空 mp.clear() 清空
unordered_map 没有：
因为它本身没有维护大小顺序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、MAP 与 UNORDERED_MAP 对比
对比 map unordered_map 底层 红黑树 哈希表 是否有序 是 否 查找 O(logn)O(\log n)O(logn) 平均 O(1)O(1)O(1) 插入 O(logn)O(\log n)O(logn) 平均 O(1)O(1)O(1) 删除 O(logn)O(\log n)O(logn) 平均 O(1)O(1)O(1) 最坏复杂度 O(logn)O(\log n)O(logn) O(n)O(n)O(n) lower_bound 支持 不支持 upper_bound 支持 不支持 前驱 / 后继 支持 不支持 适合场景 需要有序、稳定复杂度 只要求快速查找、计数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、手写哈希：线性探测
1. 核心思想
先通过哈希函数计算初始位置：
如果该位置已经被其他数字占用，就继续向后寻找：
直到：
* 找到 x
* 或找到空位置
2. 基础模板
3. 主要问题
固定哈希：
如果大量数据的哈希值集中在相邻位置，线性探测容易形成连续聚集：
此时一次查询可能需要连续检查很多位置，复杂度可能明显退化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、随机哈希
1. 作用
普通固定哈希容易被特殊数据针对：
随机哈希先将 x 打乱，再映射到哈希表：
注意：
> 随机种子只在程序开始时产生一次，同一次程序运行过程中保持不变。
因此同一个 x 每次计算得到的哈希结果仍然相同。
2. SPLITMIX64
随机种子
随机哈希
3. 随机哈希 + 线性探测模板
4. 普通哈希与随机哈希
做法 特点 x % M 简单，但规律容易被特殊数据利用 splitmix64(x + seed) 先打乱 Key，较难构造集中冲突 map 不依赖哈希，复杂度稳定为 O(logn)O(\log n)O(logn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、SET
1. 作用
set 用来维护一个：
> 有序、不重复的集合。
例如：
集合中实际为：
2. 特点
* 自动从小到大排序
* 不允许重复元素
* 底层通常为红黑树
* 插入、删除、查询复杂度均为 O(logn)O(\log n)O(logn)
3. 常用函数
写法 作用 s.insert(x) 插入 x s.erase(x) 删除 x s.find(x) 查找 x s.count(x) 判断 x 是否存在 s.lower_bound(x) 第一个 ≥x\ge x≥x 的元素 s.upper_bound(x) 第一个 >x>x>x 的元素 s.begin() 最小元素的位置 s.rbegin() 最大元素的位置 s.size() 元素数量 s.empty() 判断是否为空 s.clear() 清空
最小值与最大值
前驱与后继
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、UNORDERED_SET
1. 作用
unordered_set 用来维护：
> 无序、不重复的集合。
主要适合快速判断：
2. 特点
* 不允许重复
* 不保证遍历顺序
* 底层为哈希表
* 查询、插入、删除平均 O(1)O(1)O(1)
* 最坏可能退化到 O(n)O(n)O(n)
3. 常用函数
写法 作用 s.insert(x) 插入 s.erase(x) 删除 s.find(x) 查找 s.count(x) 判断是否存在 s.size() 元素数量 s.empty() 是否为空 s.clear() 清空
判断元素是否存在
unordered_set 不支持：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、MULTISET
1. 作用
multiset 是：
> 有序、允许重复的集合。
例如：
集合中为：
2. 特点
* 自动排序
* 允许重复
* 插入、删除、查询复杂度通常为 O(logn)O(\log n)O(logn)
* 适合需要维护重复元素、最小值、最大值、前驱后继的问题
3. 常用函数
写法 作用 s.insert(x) 插入一个 x s.count(x) x 出现次数 s.find(x) 找到某一个 x s.lower_bound(x) 第一个 ≥x\ge x≥x s.upper_bound(x) 第一个 >x>x>x s.begin() 最小值 s.rbegin() 最大值 s.size() 元素总数
4. 删除一个与删除全部
删除所有值为 X 的元素
如果集合为：
执行：
变为：
只删除一个 X
如果集合为：
只删除一个 5 后：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、SET、UNORDERED_SET、MULTISET 对比
容器 是否有序 是否允许重复 查询复杂度 lower_bound set 是 否 O(logn)O(\log n)O(logn) 支持 unordered_set 否 否 平均 O(1)O(1)O(1) 不支持 multiset 是 是 O(logn)O(\log n)O(logn) 支持
常见选择：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
