02.2.2.4 去重、布隆过滤器与 Top-K 堆
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希 / 02.2.2 字符串与哈希表
02.2.2.4-001 哈希去重的基本思路是什么?
一句话结论
用集合记录已出现的值,遇到已存在则跳过,未存在则记录并保留;平均 O(n) 时间 O(n) 空间;有序数据也可排序后相邻去重 O(n log n)。
概念解释
- 集合:存在性判断。
- 保留首次出现。
- 两种口径:保序或排序后去重。
原理流程
- 遍历元素。
- 集合未命中则保留并加入。
- 命中跳过。
代码 / 示例
Set<Integer> seen = new HashSet<>();
List<Integer> res = new ArrayList<>();
for (int x : a) {
if (seen.add(x)) res.add(x);
}
常见误区
- 误区:去重必须排序;正解:哈希保序去重,排序用于相邻去重。
- 误区:集合存重复计数;正解:存在性用 Set,计数用 Map。
追问
- Q:要求结果有序? A:排序后双指针去重,或用有序集合。
- Q:元素为对象怎么去重? A:正确实现相等判断与哈希。
02.2.2.4-002 两数组交集(LC 349 / 350)怎么做?
一句话结论
LC 349 用集合求公共元素去重;LC 350 保留重复次数,用哈希计数抵消;有序输入也可双指针 O(n+m)。
概念解释
- 349:交集元素唯一。
- 350:按出现次数取最小。
- 有序:双指针对齐。
原理流程
- 短数组入集合/计数表。
- 遍历另一数组匹配。
- 计数类命中后递减。
代码 / 示例
// 350:保留重复次数
public int[] intersect(int[] a, int[] b) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : a) cnt.merge(x, 1, Integer::sum);
List<Integer> res = new ArrayList<>();
for (int x : b) {
if (cnt.getOrDefault(x, 0) > 0) {
res.add(x);
cnt.merge(x, -1, Integer::sum);
}
}
return res.stream().mapToInt(Integer::intValue).toArray();
}
常见误区
- 误区:350 用集合去重;正解:重复次数要保留。
- 误区:两数组都有序仍用哈希;正解:有序可双指针 O(1) 额外空间。
追问
- Q:数组已排序? A:双指针:小者前移,相等记录。
- Q:一数组很小? A:小的入表,遍历大的。
02.2.2.4-003 存在性查重与计数查重怎么区分?
一句话结论
只判断出现过没有用 Set;需要知道出现几次用 Map 计数;计数题不能用集合覆盖重复,存在性题不必存次数。
概念解释
- Set:键存在性。
- Map:键 → 次数。
- 口径由题目要求决定。
原理流程
- 明确问"是否出现"还是"出现几次"。
- 选 Set 或 Map。
- 遍历更新。
代码 / 图示
存在性:Set.add / contains
计 数:Map.merge(key, 1, sum)
常见误区
- 误区:计数题用 Set 丢重复;正解:累加次数。
- 误区:存在性题存次数浪费空间;正解:Set 更省。
追问
- Q:频率统计后排序? A:Map 计数后按次数排序或入堆。
- Q:值域小用什么? A:数组计数替代哈希。
02.2.2.4-004 布隆过滤器是什么结构?
一句话结论
布隆过滤器是位数组 + 多个哈希函数:插入时把多个哈希位置置 1,查询时这些位全 1 才可能存在;空间极省,允许假阳性,不允许假阴性。
概念解释
- 位数组:初始全 0。
- 多哈希:一个键映射多个位。
- 判定:全 1 → 可能存在;有 0 → 一定不存在。
原理流程
- 初始化 m 位全 0。
- 插入:k 个哈希位置置 1。
- 查询:任一为 0 判不存在,全 1 判可能存在。
代码 / 图示
位: 0 1 0 0 1 0 1
插入 x:h1(x), h2(x), h3(x) 置 1
查询 y:对应位有 0 → 一定不在
常见误区
- 误区:布隆过滤器说存在就一定存在;正解:可能误判(假阳性)。
- 误区:说不存在也可能存在;正解:不存在是确定的(无假阴性)。
追问
- Q:为什么没有假阴性? A:插入置 1 不会变回 0,已存在的位必为 1。
- Q:布隆过滤器存原始值吗? A:不存,只存位标记。
02.2.2.4-005 布隆过滤器的误判从哪来?
一句话结论
不同键的哈希位可能重叠,未插入的键其所有位恰好被其他键置 1,形成假阳性;位数越少、元素越多,误判率越高。
概念解释
- 位重叠:多键共享位。
- 假阳性:判存在但实际不在。
- 误判率:随填充密度上升。
原理流程
- 多个键置位叠加。
- 新键位全被覆盖。
- 查询误判存在。
代码 / 图示
x 置位 {1,3},y 置位 {3,5}
z 哈希到 {1,5}:全 1 但未插入 → 假阳性
常见误区
- 误区:误判可以通过好哈希完全消除;正解:只能降低概率,不能消除。
- 误区:误判方向相反;正解:只会把不在判成在,不会把在判成不在。
追问
- Q:误判率怎么控制? A:增大位数、选合适哈希数,按元素量估算。
- Q:误判有什么影响? A:穿透到下游存储多查一次,不会漏数据。
02.2.2.4-006 布隆过滤器为什么不支持删除?
一句话结论
位被多个键共享,直接清 1 位会连带删掉其他键的标记;标准布隆过滤器不支持删除;需要删除用计数布隆过滤器或布隆过滤器变种。
概念解释
- 共享位:一位对应多键。
- 删除清位:误伤其他键。
- 变种:每位计数,支持减计数。
原理流程
- 标准结构位只有 0/1。
- 删除无法判断位是否还被占用。
- 计数版用小计数器替代位。
代码 / 图示
标准:位 1 无法区分是 x 还是 y 置的
计数版:每位存计数,删时减一到 0 清位
常见误区
- 误区:布隆过滤器可以直接删键;正解:标准结构不支持。
- 误区:计数布隆过滤器无代价;正解:计数器额外占空间。
追问
- Q:定期重建过滤器? A:删除多时重建,属于折中方案。
- Q:可删除的近似结构有哪些? A:计数布隆、Cuckoo 过滤器等,按场景选型。
02.2.2.4-007 布隆过滤器参数怎么估算?
一句话结论
给定元素数 n 与期望误判率 p,位数 m = -n·ln p / (ln2)²,最优哈希数 k = m/n · ln2;工程上按内存预算反推误判率。
概念解释
- m:位数。
- k:哈希函数个数。
- 关系:空间、误判率、哈希数折中。
原理流程
- 确定 n 与可接受 p。
- 代入公式算 m、k。
- 位数组与哈希函数落地。
代码 / 图示
m ≈ -n·ln p / (ln2)²
k ≈ (m/n)·ln2
常见误区
- 误区:哈希越多越准;正解:k 过大会快速填满位,误判反升。
- 误区:位数固定随意插;正解:超载后误判率急剧上升。
追问
- Q:Redis 布隆过滤器参数? A:按实际配置,具体实现以版本为准。
- Q:误判率 1% 大约多少位/元素? A:按公式估算,约 9.6 位/元素量级。
02.2.2.4-008 布隆过滤器用在什么场景?
一句话结论
放在缓存/数据库前拦截一定不存在的请求,避免穿透到下游;典型如缓存击穿、垃圾邮件过滤、URL 去重;允许小概率误判换取空间与速度。
概念解释
- 缓存穿透:查询不存在数据打到 DB。
- 前置拦截:过滤器判不存在直接返回。
- 容忍误判:漏到下游一次无害。
原理流程
- 预热:把已有键灌入过滤器。
- 查询:先过过滤器。
- 判不存在直接拒绝;判存在再查缓存/DB。
代码 / 图示
请求 → 布隆过滤器
不存在 → 直接返回
可能存在 → 查缓存 → DB
常见误区
- 误区:布隆过滤器替代缓存;正解:它只做存在性前置,不存值。
- 误区:强一致场景使用;正解:假阳性可能多查,不能用于必须精确判定处。
追问
- Q:数据下架怎么处理? A:标准过滤器无法删,靠重建或变种。
- Q:误判请求落到 DB 有什么防护? A:配合空值缓存、限流等手段。
02.2.2.4-009 Top-K 问题一般指什么?
一句话结论
从 n 个元素中求最大/最小的 K 个,或第 K 大/小;常见解法:全排序 O(n log n)、堆 O(n log K)、快速选择平均 O(n)。
概念解释
- 最大 K / 最小 K。
- 第 K 名。
- 数据流:元素持续到达。
原理流程
- 明确求 K 个还是第 K 个。
- 按数据是否全量可选结构。
- 评估时间空间。
代码 / 图示
全排序:O(n log n)
堆:O(n log K)
快速选择:平均 O(n)
常见误区
- 误区:Top-K 必须全排序;正解:堆或快速选择更省。
- 误区:K 接近 n 时堆仍最优;正解:K 很大时全排序或其他方法常数更优。
追问
- Q:K=1 求最值? A:一次扫描 O(n),无需堆。
- Q:数据流不断来? A:堆在线维护 K 个候选。
02.2.2.4-010 小顶堆为什么求最大 K 个?
一句话结论
小顶堆堆顶是堆内最小值;维护 K 个最大元素,新元素比堆顶大则替换堆顶,最终堆内即最大 K 个;O(n log K) 时间 O(K) 空间。
概念解释
- 堆大小 K。
- 堆顶为候选中最弱。
- 劣值替换。
原理流程
- 前 K 个入小顶堆。
- 后续元素大于堆顶则弹出堆顶、入堆。
- 结束堆内为最大 K。
代码 / 示例
public int[] topK(int[] a, int k) {
Queue<Integer> heap = new PriorityQueue<>();
for (int x : a) {
heap.offer(x);
if (heap.size() > k) heap.poll();
}
return heap.stream().mapToInt(Integer::intValue).toArray();
}
常见误区
- 误区:求最大 K 用大顶堆;正解:小顶堆便于淘汰最小候选。
- 误区:堆内顺序即答案顺序;正解:堆内无序,需再排序输出。
追问
- Q:求最小 K 个用什么堆? A:大顶堆,堆顶为候选中最大。
- Q:K ≥ n? A:直接返回全部,无需堆。
02.2.2.4-011 前 K 个高频元素(LC 347)怎么做?
一句话结论
哈希计数后用小顶堆按频率维护 K 个键;O(n log K) 时间 O(n) 空间;也可用桶排序按频率分组 O(n)。
概念解释
- 计数:键 → 次数。
- 堆:按频率比较。
- 桶法:频率范围有限时分组。
原理流程
- 一遍统计频率。
- 堆维护 K 个高频键。
- 输出堆内键。
代码 / 示例
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
Queue<Map.Entry<Integer, Integer>> heap =
new PriorityQueue<>(Map.Entry.comparingByValue());
for (var e : cnt.entrySet()) {
heap.offer(e);
if (heap.size() > k) heap.poll();
}
return heap.stream().mapToInt(Map.Entry::getKey).toArray();
}
常见误区
- 误区:堆按键值比较;正解:按频率比较。
- 误区:先对全量频率排序;正解:堆只维护 K 个候选。
追问
- Q:桶排序做法? A:频率作下标分组,从高到低取满 K 个,O(n)。
- Q:频率相同怎么排? A:按题目口径,题目不要求次序时任意。
02.2.2.4-012 堆与全排序做 Top-K 怎么对比?
一句话结论
全排序 O(n log n) 得到有序全量;堆 O(n log K) 只维护 K 个候选;K 小堆更优,K 接近 n 时全排序常数可能更划算。
概念解释
- 堆:部分排序。
- 全排序:整体有序。
- 权衡:K 大小与是否需要有序输出。
原理流程
- 看 K 与 n 比例。
- 小 K 用堆。
- 需要全量有序则排序。
代码 / 图示
K ≪ n:堆 O(n log K)
K ≈ n:全排序 O(n log n)
输出需有序:堆内再排序 O(K log K)
常见误区
- 误区:堆一定比排序快;正解:K 大时堆的 log K 接近 log n。
- 误区:堆输出天然有序;正解:堆内无序,需额外排序。
追问
- Q:K=1 堆还有必要吗? A:一次扫描记录最值即可。
- Q:稳定输出顺序? A:按频率排序后输出,必要时次键排序。
02.2.2.4-013 快速选择求第 K 大是什么思路?
一句话结论
基于快排分区:选基准把数组划分为两侧,按基准位置与 K 的关系只递归一侧;平均 O(n),最坏 O(n²);求得第 K 名后可取周围 K 个。
概念解释
- 分区:小于基准 / 大于基准。
- 单侧递归:根据目标位置放弃另一侧。
- 平均线性:每层扫描总量递减。
原理流程
- 分区得基准下标。
- 与 K 比较决定递归侧。
- 命中返回。
代码 / 图示
partition → pivot 位置
位置 == K → 答案
位置 < K → 递归右侧
位置 > K → 递归左侧
常见误区
- 误区:快速选择最坏也是 O(n);正解:最坏 O(n²),随机基准降低概率。
- 误区:快速选择得到有序 Top-K;正解:只定位第 K 名,两侧不保证有序。
追问
- Q:最坏怎么避免? A:随机选基准或三数取中。
- Q:需要输出 K 个元素? A:定位第 K 名后收集一侧,必要时排序。
02.2.2.4-014 数据流 Top-K 怎么在线维护?
一句话结论
新元素到达时与堆内候选比较,满足条件则替换堆顶;堆大小恒定 K,O(log K) 单次维护;不保存全量数据,适合流式场景。
概念解释
- 流式:数据不全量持有。
- 堆:固定 K 候选。
- 在线:每来一个更新一次。
原理流程
- 堆预填前 K 个。
- 新元素比较堆顶。
- 优则替换,劣则丢弃。
代码 / 图示
来一个 x:
堆不满 → 入堆
x > 堆顶(最大 K 场景)→ 弹堆顶入堆
常见误区
- 误区:数据流先存全量再排序;正解:内存受限时堆在线维护。
- 误区:堆大小随流增长;正解:恒定 K,超出即淘汰。
追问
- Q:流中元素会过期怎么办? A:配合时间窗或延迟删除机制。
- Q:分布式数据流 Top-K? A:分片本地 Top-K 后汇总,属扩展话题。
02.2.2.4-015 堆操作的复杂度是多少?
一句话结论
入堆、出堆 O(log K),取堆顶 O(1);建堆可 O(K);n 个元素维护大小 K 的堆整体 O(n log K)。
概念解释
- 上浮/下沉:沿堆高调整。
- 堆高 log K。
- 建堆:批量自底向上 O(K)。
原理流程
- 入堆:末尾插入后上浮。
- 出堆:堆顶换末尾后下沉。
- 堆高对数级。
代码 / 图示
offer/poll:O(log K)
peek:O(1)
建堆:O(K)
常见误区
- 误区:堆插入 O(1);正解:需上浮到合法位置 O(log K)。
- 误区:堆可以 O(1) 取第 K 个;正解:堆顶只是最值,第 K 名需遍历或排序。
追问
- Q:Java PriorityQueue 是堆吗? A:基于堆实现,默认小顶堆。
- Q:堆是有序结构吗? A:只保证堆序,不保证全序。
02.2.2.4-016 去重与 Top-K 怎么结合?
一句话结论
先哈希去重/计数,再对唯一键按频次或值入堆;去重保证候选集合无重复,堆负责选优;两步串联,时间 O(n + u log K),u 为唯一键数。
概念解释
- 第一步:集合/Map 整理唯一键。
- 第二步:堆选 Top-K。
- 计数类按频次入堆。
原理流程
- 遍历去重或计数。
- 唯一键入堆比较。
- 输出堆内结果。
代码 / 图示
原始 n → 唯一 u
哈希去重/计数 O(n)
堆维护 K:O(u log K)
常见误区
- 误区:重复元素多次入堆;正解:先按键去重再选优。
- 误区:频次更新后堆内键未同步;正解:计数固定后再入堆。
追问
- Q:边流边去重边选优? A:哈希记录已见,堆维护候选,在线完成。
- Q:相同值不同对象? A:先定义相等口径再去重。
02.2.2.4-017 计数排序/桶排序在去重统计中的角色?
一句话结论
值域有限时按值或频率分桶,免比较完成统计与分组;频率桶可 O(n) 取出高频元素;值域大则退化,改用哈希与堆。
概念解释
- 值桶:按元素值分组。
- 频率桶:按出现次数分组。
- 适用:范围可数且有限。
原理流程
- 统计计数。
- 按值域/频率分桶。
- 从桶中取结果。
代码 / 图示
频率桶:bucket[f] = 出现 f 次的键
从最高频桶向下取满 K 个
常见误区
- 误区:桶排序适用于任意大范围值;正解:值域过大桶数组不可开。
- 误区:桶内自动有序;正解:桶内顺序需另行处理。
追问
- Q:LC 347 桶法复杂度? A:O(n),空间 O(n)。
- Q:负数/散值怎么分桶? A:用哈希映射再分组。
02.2.2.4-018 存在性场景如何在哈希表与布隆过滤器间选型?
一句话结论
需要精确存在性、可取回值用哈希表;海量数据、只做前置拦截、容忍小概率误判用布隆过滤器;两者可组合:过滤器先挡,哈希表/缓存确认。
概念解释
- 哈希表:精确、存值、空间大。
- 布隆:近似、不存值、空间省。
- 组合:过滤 + 精确查询。
原理流程
- 判断是否需要精确与取值。
- 评估数据量与误判容忍。
- 选结构或组合。
代码 / 图示
精确取键值 → 哈希表
海量前置拦截 → 布隆过滤器
组合:布隆挡不存在 → 哈希/存储确认
常见误区
- 误区:布隆过滤器能替代缓存;正解:它不存值,只判存在性。
- 误区:哈希表空间紧张就换布隆;正解:先确认业务能接受假阳性。
追问
- Q:布隆过滤器误判会读到什么? A:到下游查一次未命中,可缓存空结果。
- Q:需要删除键的存在性结构? A:标准布隆不支持,评估计数版或有序集合。
02.2.2.4-019 Top-K 题有哪些边界用例?
一句话结论
K=1、K=n、元素全相同、含负数、重复频次、空输入、K 超出元素数;验证堆边界、去重与返回口径。
概念解释
- K 边界:1 与 n。
- 分布:全相同、重复频次。
- 规模:空与超界。
原理流程
- 校验 K 与 n 关系。
- 构造全相同与负数用例。
- 核对返回数量与顺序。
代码 / 图示
K=1 / K=n / K>n
全相同 / 频次并列
空数组 / 负数与零
常见误区
- 误区:K>n 未处理;正解:按口径返回全部或报错。
- 误区:全相同堆内替换无意义;正解:结果全部相同,仍按数量返回。
追问
- Q:频次并列如何取舍? A:按题目口径,不要求次序时任意。
- Q:空输入返回什么? A:空数组/空列表。
02.2.2.4-020 去重与 Top-K 题复杂度怎么汇报?
一句话结论
去重:哈希 O(n) 时间 O(n) 空间,排序去重 O(n log n);Top-K:堆 O(n log K) 时间 O(K),快速选择平均 O(n);汇报时分预处理与选优两段。
概念解释
- 预处理:去重/计数。
- 选优:堆或选择。
- 空间:哈希表 + 候选结构。
原理流程
- 标注去重/计数代价。
- 标注选优结构代价。
- 辅助空间分列。
代码 / 图示
哈希去重:O(n) 时间 / O(n) 空间
堆 Top-K:O(n log K) 时间 / O(K) 空间
快速选择:平均 O(n) 时间 / O(1) 额外(递归栈另计)
常见误区
- 误区:只报堆的 log K 不提计数;正解:预处理 O(n) 一并说明。
- 误区:快速选择承诺最坏 O(n);正解:平均 O(n),最坏 O(n²)。
追问
- Q:输出有序是否加代价? A:堆内 K 个再排序 O(K log K)。
- Q:布隆过滤器空间怎么估? A:按位数 m 与哈希数 k,误判率见参数估算。