LeetCode笔记：剑指Offer41.数据流中的中位数（Java、堆、优先队列、知识点）

打卡第十一天&＃xff5e;

题目描述

• 虽然但是&＃xff0c;这是一道很nice的题目&＃xff08;涉及的知识点、运用很实用&＃xff0c;见知识点模块&＃xff09;
  
  

知识点

1. 优先队列

• priorityQueue 是 Queue 接口的实现&＃xff0c;可以对其中元素进行排序。
• 默认顺序是升序&＃xff1b;采用的是堆排序&＃xff08;小顶堆&＃xff09;&＃xff0c;因此只能保证根是最值&＃xff0c;整个堆并不是有序的。
• 自定义比较类&＃xff1a;在 priorityQueue 的构造函数参数中用 Lambda 表达式表示即可。

2. Java 中 queue 的 offer、poll 等区别

• add、offer&＃xff1a;都是添加&＃xff1b;队满情况 add 抛出异常&＃xff0c;而 offer 则返回 false&＃xff0c;可用于判断
• remove、poll&＃xff1a;都是删除首元素&＃xff1b;队空情况remove抛出异常&＃xff0c;而 poll 返回 null
• element、peek&＃xff1a;都是查询首元素&＃xff1b;队空情况element抛出异常&＃xff0c;而peek 返回 null

思路 && 代码

• 代码量不大&＃xff0c;主要考察的思路&＃xff5e;
• 首先中位数需要考虑总数奇偶情况&＃xff1a;奇取中值&＃xff0c;偶取平均值。
• 然后既然想获得好的时间复杂度&＃xff0c;那就空间换时间了&＃xff08;否则数组慢慢来也行了&＃xff09;
• 接着&＃xff0c;既然中位数是在排序后元素集的中间&＃xff0c;那么我们可以有这么一个考虑&＃xff1a;中间靠两个数据结构实现&＃xff08;毕竟一半一半嘛&＃xff01;&＃xff09;&＃xff0c;而有序&＃xff08;或局部有序&＃xff09;的数据结构中&＃xff0c;进行 add 操作的时间复杂度最低的(O(logn))就是堆了&＃xff01;
• 因此&＃xff0c;我们选取优先队列来作为实现的数据结构&＃xff5e;
• 主要思路&＃xff1a;大顶堆存储较小部分&＃xff0c;小顶堆存储较大部分。通过两个堆的堆顶来取中位数。通过先添加到堆a&＃xff0c;再添加堆a的堆顶到堆b的“洗元素”方式来维护较大、较小的属性。

class MedianFinder {Queue<Integer> smallHeap, bigHeap;/** initialize your data structure here. */public MedianFinder() {// 各存一半&＃xff1a;small 小顶堆存储较大部分&＃xff1b;big 大顶堆存储较小部分smallHeap &＃61; new PriorityQueue<>();bigHeap &＃61; new PriorityQueue<>((x, y) -> (y - x));}// 维护两个 Heap 的较大、较小属性&＃xff1a;O(logn)public void addNum(int num) {// N &＃61; 奇数&＃xff1a;增加 bigHeap 元素&＃xff0c;通过先添加到 smallHeap&＃xff0c;再获取其堆顶实现if(smallHeap.size() !&＃61; bigHeap.size()) {smallHeap.add(num);bigHeap.add(smallHeap.poll());} // N &＃61; 偶数&＃xff1a;增加 small 元素&＃xff0c;通过先添加到 bigHeap&＃xff0c;再获取其堆顶实现else {bigHeap.add(num);smallHeap.add(bigHeap.poll());}}// O(1)public double findMedian() {// 偶数情况if(smallHeap.size() &＃61;&＃61; bigHeap.size()) {// 较大堆的最小值 &＃43; 较小堆里的最大值return (smallHeap.peek() &＃43; bigHeap.peek()) / 2.0;}// 奇数情况else {return smallHeap.peek();}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj &＃61; new MedianFinder();* obj.addNum(num);* double param_2 &＃61; obj.findMedian();*/


二刷

• 关键词&＃xff1a;优先队列、堆之间洗数据、Lambda 表达式
• 思路还是难忘&＃xff0c;代码也不多。这道题保持 hard 的时间估计不长了…

class MedianFinder {Queue<Integer> smallTop &＃61; new PriorityQueue<>();Queue<Integer> bigTop &＃61; new PriorityQueue<>((x, y) -> (y - x));public MedianFinder() {}public void addNum(int num) {if(smallTop.size() &＃61;&＃61; bigTop.size()) {bigTop.add(num);smallTop.add(bigTop.poll());}else {smallTop.add(num);bigTop.add(smallTop.poll());}}public double findMedian() {if(smallTop.size() &＃61;&＃61; bigTop.size()) {return (smallTop.peek() &＃43; bigTop.peek()) / 2.0;}else {return smallTop.peek();}}
}