CS-Notes 剑指 Offer 41.1 数据流中的中位数：用两个堆在线维护中位数

CS-Notes 剑指 Offer 41.1 数据流中的中位数用两个堆在线维护中位数【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 仓库中的题解文档 41.1 数据流中的中位数讲解如何在元素逐个到达、无法一次性排序的数据流场景下用大顶堆 小顶堆的对偶结构把中位数查询做到 O(1)、插入做到 O(log N)。读完本篇你将掌握该题完整的 Java 实现、两个堆必须维持的不变式证明思路以及它与仓库中同系列的最小的 K 个数共用的大顶堆技巧。题目描述本题出自《剑指 Offer》第 41 题的第一问属于仓库剑指 Offer 题解 - 目录中栈队列堆分类下的典型题目原题在线练习平台为牛客网。如何得到一个数据流中的中位数如果从数据流中读出奇数个数值那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值那么中位数就是所有数值排序之后中间两个数的平均值。题目给出了两个操作接口Insert(Integer val)数据流来一个新元素需要插入GetMedian()随时查询当前已读入全部元素的中位数。难点在于**流式 任意时刻可查询**元素是陆续到达的任何时刻都可能被要求给出中位数因此不能来一批再排序必须用某种数据结构在插入时就维护好中位数所需的信息。解题思路大顶堆存左半边小顶堆存右半边朴素做法是维护一个有序数组每次插入 O(N)、查询 O(1)或者每次查询时现排插入 O(1)、查询 O(N log N)。两种方案都偏科无法同时满足插入快、查询也快。官方题解采用的核心思想是用两个堆把数据流对半切让中位数永远落在两个堆顶的交汇处成员变量类型职责leftPriorityQueueInteger比较器(o1, o2) - o2 - o1即大顶堆存储排序后左半边较小的一半元素堆顶是左半边的最大值rightPriorityQueueInteger默认比较器即小顶堆存储排序后右半边较大的一半元素堆顶是右半边的最小值Nint当前数据流已读入的元素个数这里涉及的两个堆正是仓库 Java 容器 中介绍的 Queue 分类下的PriorityQueue——基于堆结构实现可以用它来实现优先队列默认是小顶堆初始化时传入比较器即可反转为大顶堆。两个必须维持的不变式整个算法正确性依赖以下两条不变式invariant有序性不变式right中的每个元素都大于等于left中的每个元素。这样两个堆顶就是整个数据集排序后正中间的 1 个或 2 个元素规模平衡不变式两堆大小相差不超过 1且奇偶关系由N决定——N为奇数时right比left多一个元素N为偶数时两堆等大。维持住这两条不变式后中位数查询就是 O(1)N为奇数中位数是排序后的中间一个数恰好是right的堆顶右半边的最小值N为偶数中位数是中间两数的平均值恰好是left.peek() right.peek()的平均值。Insert先插入错误的一边再把堆顶挪到另一边Insert的写法看似绕其实是在利用堆顶特性以 O(log N) 完成跨堆搬运从而保证有序性不变式/* 大顶堆存储左半边元素 */ private PriorityQueueInteger left new PriorityQueue((o1, o2) - o2 - o1); /* 小顶堆存储右半边元素并且右半边元素都大于左半边 */ private PriorityQueueInteger right new PriorityQueue(); /* 当前数据流读入的元素个数 */ private int N 0; public void Insert(Integer val) { /* 插入要保证两个堆存于平衡状态 */ if (N % 2 0) { /* N 为偶数的情况下插入到右半边。 * 因为右半边元素都要大于左半边但是新插入的元素不一定比左半边元素来的大 * 因此需要先将元素插入左半边然后利用左半边为大顶堆的特点 * 取出堆顶元素即为最大元素此时插入右半边 */ left.add(val); right.add(left.poll()); } else { right.add(val); left.add(right.poll()); } N; }逐分支解释这是原文档给出的完整实现逐行注释如下N 为偶数此时两堆等大插入后应由right变多一个目标边是right但新元素val完全可能比left里某些元素还小不能直接扔进right。于是先把val塞进left大顶堆此时left的堆顶就是左半边 val中的最大值把它poll出来放进right。这个最大值正是排序后应该属于右半边的最小那个数一次add 一次poll就同时完成了入堆与修正归属N 为奇数此时right多一个元素插入后应由left变多一个对称操作——先right.add(val)再把right堆顶右半边最小值搬进left。每轮插入都恰好发生一次跨堆搬运所以规模平衡不变式天然成立无需额外的 rebalance 逻辑。GetMedian只读堆顶O(1) 返回public Double GetMedian() { if (N % 2 0) return (left.peek() right.peek()) / 2.0; else return (double) right.peek(); }N为偶数两堆等大中间两个数就是left的最大值与right的最小值。注意除以2.0触发浮点除法避免整数截断N为奇数中间那个数就是right的堆顶强转double后返回。两个方法都只用到peekO(1)配合Insert的两次堆操作得到整体复杂度操作时间复杂度说明InsertO(log N)一次add 一次poll均为 O(log N)GetMedianO(1)仅读堆顶空间O(N)N 个元素全部分布在两个堆中对比数组排序方案查询 O(1) 但插入 O(N)或查询 O(N)双堆方案把两个操作都压到对数以内这正是它适合数据流场景的原因。执行过程走查以插入序列 5、2、3、4 为例按上面的代码逐步跟踪可以直观看到不变式如何被维持步骤操作left大顶堆堆顶在前right小顶堆堆顶在前N 后GetMedian验证全量排序1Insert(5)[5] → 搬出 5[5]15.0[5] → 5 ✓2Insert(2)[2]2 先入 left再与 5 比较后留下[5]2(25)/2 3.5[2,5] → 3.5 ✓3Insert(3)[3, 2]3 先入 left3 出堆顶[3, 5]33.0[2,3,5] → 3 ✓4Insert(4)[3, 2]4 先入 right3 出堆顶[4, 5]4(34)/2 3.5[2,3,4,5] → 3.5 ✓注意第 2 步val 2小于左半边已有的 5它先入left后堆顶仍是 55 被搬到right2 留在left——这正是新元素不一定比左半边大时该分支存在的意义。第 4 步则相反val 4进入right后堆顶是最小的 33 被搬回left。无论哪种情况搬动的总是当前跨界的那个元素。细节与易错点比较器溢出隐患仓库题解与 40. 最小的 K 个数 一致用(o1, o2) - o2 - o1实现大顶堆。做减法在极端值下可能溢出例如o1 Integer.MIN_VALUE更稳妥的等价写法是(o1, o2) - Integer.compare(o2, o1)面试中说明这一点是加分项。偶数个数时除的是 2.0(left.peek() right.peek()) / 2.0若写成/ 2会做整数除法截断小数。堆的归属只约束跨界元素本方案从不移动堆内普通元素每次插入只做一次堆顶搬运这是 O(log N) 复杂度的来源也是它与两个有序列表手动 rebalance方案的本质区别。空流与查询时机接口约定GetMedian在已插入元素后调用N计数即用来判断当前属于奇数还是偶数情形无需额外调用size()。为什么不用别的方案数组 每次排序查询快但插入 O(N)数据流持续增长时总代价劣于堆平衡二叉搜索树如 TreeSetJava 的TreeSet基于红黑树见 Java 容器 中 Set 分类也能做到插入/查询 O(log N)但要取第 N/2 个位置仍需额外维护索引或顺序统计双堆方案更简单且只关心中间一个/两个位置堆顶恰好就是答案是最贴合题意的结构快速选择QuickSelect单次求中位数 O(N)但无法在每次插入后低成本复用不适合任意时刻查询的流式场景。仓库中快速选择的思想可见 40. 最小的 K 个数 的第二个方案适合一次性离线求解与本在线场景正好互补。仓库中的相关题解最小的 K 个数与本题共用大顶堆 堆顶即当前极值的技巧该题解还专门强调应该使用大顶堆来维护最小堆以及PriorityQueue比较器的用法41.2 字符流中第一个不重复的字符同属流式插入 即时查询题型用频次数组 队列维护答案可与双堆方案对照体会流式问题的通用解法思路剑指 Offer 题解 - 目录本题归类于栈队列堆章节可顺藤摸瓜练习同分类的9. 用两个栈实现队列、59. 滑动窗口的最大值等。小结数据流中位数问题的关键是把中位数转化为两个堆顶left大顶堆存较小一半、right小顶堆存较大一半插入时通过先入目标侧的对面、再搬堆顶的一次跨堆操作同时完成入堆与归属修正从而在 O(log N) 插入、O(1) 查询下任意时刻返回正确中位数。完整可运行代码见仓库题解 41.1 数据流中的中位数配合上文走查表验证每一步后可以直接在刷题平台上实现Insert与GetMedian两个方法。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考