罗罗编程学习记录
本页内容 展开查看

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)。

概念解释

  • 集合:存在性判断。
  • 保留首次出现。
  • 两种口径:保序或排序后去重。

原理流程

  1. 遍历元素。
  2. 集合未命中则保留并加入。
  3. 命中跳过。

代码 / 示例

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:按出现次数取最小。
  • 有序:双指针对齐。

原理流程

  1. 短数组入集合/计数表。
  2. 遍历另一数组匹配。
  3. 计数类命中后递减。

代码 / 示例

// 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:键 → 次数。
  • 口径由题目要求决定。

原理流程

  1. 明确问"是否出现"还是"出现几次"。
  2. 选 Set 或 Map。
  3. 遍历更新。

代码 / 图示

存在性: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 → 一定不存在。

原理流程

  1. 初始化 m 位全 0。
  2. 插入:k 个哈希位置置 1。
  3. 查询:任一为 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,形成假阳性;位数越少、元素越多,误判率越高。

概念解释

  • 位重叠:多键共享位。
  • 假阳性:判存在但实际不在。
  • 误判率:随填充密度上升。

原理流程

  1. 多个键置位叠加。
  2. 新键位全被覆盖。
  3. 查询误判存在。

代码 / 图示

x 置位 {1,3},y 置位 {3,5}
z 哈希到 {1,5}:全 1 但未插入 → 假阳性

常见误区

  • 误区:误判可以通过好哈希完全消除;正解:只能降低概率,不能消除。
  • 误区:误判方向相反;正解:只会把不在判成在,不会把在判成不在。

追问

  • Q:误判率怎么控制? A:增大位数、选合适哈希数,按元素量估算。
  • Q:误判有什么影响? A:穿透到下游存储多查一次,不会漏数据。

02.2.2.4-006 布隆过滤器为什么不支持删除?

一句话结论

位被多个键共享,直接清 1 位会连带删掉其他键的标记;标准布隆过滤器不支持删除;需要删除用计数布隆过滤器或布隆过滤器变种。

概念解释

  • 共享位:一位对应多键。
  • 删除清位:误伤其他键。
  • 变种:每位计数,支持减计数。

原理流程

  1. 标准结构位只有 0/1。
  2. 删除无法判断位是否还被占用。
  3. 计数版用小计数器替代位。

代码 / 图示

标准:位 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:哈希函数个数。
  • 关系:空间、误判率、哈希数折中。

原理流程

  1. 确定 n 与可接受 p。
  2. 代入公式算 m、k。
  3. 位数组与哈希函数落地。

代码 / 图示

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。
  • 前置拦截:过滤器判不存在直接返回。
  • 容忍误判:漏到下游一次无害。

原理流程

  1. 预热:把已有键灌入过滤器。
  2. 查询:先过过滤器。
  3. 判不存在直接拒绝;判存在再查缓存/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 名。
  • 数据流:元素持续到达。

原理流程

  1. 明确求 K 个还是第 K 个。
  2. 按数据是否全量可选结构。
  3. 评估时间空间。

代码 / 图示

全排序: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。
  • 堆顶为候选中最弱。
  • 劣值替换。

原理流程

  1. 前 K 个入小顶堆。
  2. 后续元素大于堆顶则弹出堆顶、入堆。
  3. 结束堆内为最大 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)。

概念解释

  • 计数:键 → 次数。
  • 堆:按频率比较。
  • 桶法:频率范围有限时分组。

原理流程

  1. 一遍统计频率。
  2. 堆维护 K 个高频键。
  3. 输出堆内键。

代码 / 示例

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 大小与是否需要有序输出。

原理流程

  1. 看 K 与 n 比例。
  2. 小 K 用堆。
  3. 需要全量有序则排序。

代码 / 图示

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 个。

概念解释

  • 分区:小于基准 / 大于基准。
  • 单侧递归:根据目标位置放弃另一侧。
  • 平均线性:每层扫描总量递减。

原理流程

  1. 分区得基准下标。
  2. 与 K 比较决定递归侧。
  3. 命中返回。

代码 / 图示

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 候选。
  • 在线:每来一个更新一次。

原理流程

  1. 堆预填前 K 个。
  2. 新元素比较堆顶。
  3. 优则替换,劣则丢弃。

代码 / 图示

来一个 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)。

原理流程

  1. 入堆:末尾插入后上浮。
  2. 出堆:堆顶换末尾后下沉。
  3. 堆高对数级。

代码 / 图示

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。
  • 计数类按频次入堆。

原理流程

  1. 遍历去重或计数。
  2. 唯一键入堆比较。
  3. 输出堆内结果。

代码 / 图示

原始 n → 唯一 u
哈希去重/计数 O(n)
堆维护 K:O(u log K)

常见误区

  • 误区:重复元素多次入堆;正解:先按键去重再选优。
  • 误区:频次更新后堆内键未同步;正解:计数固定后再入堆。

追问

  • Q:边流边去重边选优? A:哈希记录已见,堆维护候选,在线完成。
  • Q:相同值不同对象? A:先定义相等口径再去重。

02.2.2.4-017 计数排序/桶排序在去重统计中的角色?

一句话结论

值域有限时按值或频率分桶,免比较完成统计与分组;频率桶可 O(n) 取出高频元素;值域大则退化,改用哈希与堆。

概念解释

  • 值桶:按元素值分组。
  • 频率桶:按出现次数分组。
  • 适用:范围可数且有限。

原理流程

  1. 统计计数。
  2. 按值域/频率分桶。
  3. 从桶中取结果。

代码 / 图示

频率桶:bucket[f] = 出现 f 次的键
从最高频桶向下取满 K 个

常见误区

  • 误区:桶排序适用于任意大范围值;正解:值域过大桶数组不可开。
  • 误区:桶内自动有序;正解:桶内顺序需另行处理。

追问

  • Q:LC 347 桶法复杂度? A:O(n),空间 O(n)。
  • Q:负数/散值怎么分桶? A:用哈希映射再分组。

02.2.2.4-018 存在性场景如何在哈希表与布隆过滤器间选型?

一句话结论

需要精确存在性、可取回值用哈希表;海量数据、只做前置拦截、容忍小概率误判用布隆过滤器;两者可组合:过滤器先挡,哈希表/缓存确认。

概念解释

  • 哈希表:精确、存值、空间大。
  • 布隆:近似、不存值、空间省。
  • 组合:过滤 + 精确查询。

原理流程

  1. 判断是否需要精确与取值。
  2. 评估数据量与误判容忍。
  3. 选结构或组合。

代码 / 图示

精确取键值 → 哈希表
海量前置拦截 → 布隆过滤器
组合:布隆挡不存在 → 哈希/存储确认

常见误区

  • 误区:布隆过滤器能替代缓存;正解:它不存值,只判存在性。
  • 误区:哈希表空间紧张就换布隆;正解:先确认业务能接受假阳性。

追问

  • Q:布隆过滤器误判会读到什么? A:到下游查一次未命中,可缓存空结果。
  • Q:需要删除键的存在性结构? A:标准布隆不支持,评估计数版或有序集合。

02.2.2.4-019 Top-K 题有哪些边界用例?

一句话结论

K=1、K=n、元素全相同、含负数、重复频次、空输入、K 超出元素数;验证堆边界、去重与返回口径。

概念解释

  • K 边界:1 与 n。
  • 分布:全相同、重复频次。
  • 规模:空与超界。

原理流程

  1. 校验 K 与 n 关系。
  2. 构造全相同与负数用例。
  3. 核对返回数量与顺序。

代码 / 图示

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);汇报时分预处理与选优两段。

概念解释

  • 预处理:去重/计数。
  • 选优:堆或选择。
  • 空间:哈希表 + 候选结构。

原理流程

  1. 标注去重/计数代价。
  2. 标注选优结构代价。
  3. 辅助空间分列。

代码 / 图示

哈希去重: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,误判率见参数估算。