文章目录
- 前言
- 数据流中的中位数的问题
- 总结
前言
提示：我独自度过了太多的时光，沉默已成一种习惯。 帕瑞尔·马卡姆《夜航西飞》
这个是一个比较难的题目，要不尝试一下看看。
数据流中的中位数的问题
参考题目地址：295. 数据流的中位数 - 力扣（LeetCode）
进阶问题：
- 如果数据流中所有整数都在0到100范围内呢，你将如何优化你的算法？
- 如果数据流中99%的整数都在0到100范围内呢？你将如何优化你的算法？
我们分析一下：
这道题说真的挺难的，如果没有专门的学过，很难再面试中想到。
中位数的题目，我们一般可以采用 大顶堆 + 小顶堆 来求解，下面我们通过直观的例子了解下怎么处理：
小顶堆：存储所有元素中较大的一半，堆顶存储的其实是最小的数。
大顶堆：存储所有元素中较小的一半，堆顶存储的其实是最大的数。
相当于，把所有元素分成大小两半，而我们计算中位数，只需要大的那半的最小值和小的那半的最大值就可以了。
比如：我们依次添加【1，2，3，4，5】，砍成两半为【1，2】和【3，4，5】。我们是需要快速找到 2 和 3 就可以了。
下面我们看看两个堆是怎么变化的：
- 添加1，进入minHeap中，中位数为1
- 添加2 ，它比minHeap堆顶的元素大1，进入minHeap，minHeap中的元素超过所有元素总和的一半，所以要平衡一下，分给maxHeap，中位数为（1 + 2 ）/ 2 = 1.5；
- 添加 3 ，它比minHeap堆顶元素2 大，进入minHeap，中位数为2；
- 添加4 ，它比minHeap堆顶的元素2大，进入minHeap，minHeap中的元素超过所有元素总和的一半，所以要平衡一下，分给maxHeap，中位数为（2+ 3 ）/ 2 = 2.5；
- 添加 5，它比minHeap堆顶元素3 大，进入minHeap，中位数为3；
Java中堆（即使优先队列）是使用完全二叉树实现的。理解以下，我们看代码怎么做，代码写起来比较简单，但是实现起来还挺麻烦的。
class MedianFinder {// 这里小顶堆 存储较大的一半（最小值在堆顶PriorityQueue<Integer> minHeap;// 这里大顶堆 存储较小的一半（最大值在堆顶PriorityQueue<Integer> maxHeap;public MedianFinder() {minHeap = new PriorityQueue<>();maxHeap = new PriorityQueue<>((a,b) -> b - a);}public void addNum(int num) {// 小顶堆存储大的元素，num只要大于元素中最小的，就入堆if(minHeap.isEmpty() || num > minHeap.peek()){minHeap.offer(num);if(minHeap.size() - maxHeap.size() > 1){maxHeap.offer(minHeap.poll());}}else{maxHeap.offer(num);// 可以确保多的那个元素一定在minHeapif(maxHeap.size() - minHeap.size() > 0){minHeap.offer(maxHeap.poll());}}}public double findMedian() {if(minHeap.size() > maxHeap.size()){return minHeap.peek();}else if(minHeap.size() < maxHeap.size()){return maxHeap.peek();}else{return (minHeap.peek() + maxHeap.peek()) / 2.0;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/
总结
提示：堆的经典应用；大顶堆小顶堆；中位数问题；特殊解法；优先队列（priority)：
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/ 如有不理解的地方，欢迎你在评论区给我留言，我都会逐一回复 ~ 也欢迎你 关注我 ，喜欢交朋友，喜欢一起探讨问题。
