295. 数据流的中位数解题思路（通俗易懂大小堆解法）
题目描述
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
-
MedianFinder()初始化MedianFinder对象。 -
void addNum(int num)将数据流中的整数num添加到数据结构中。 -
double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0]
解决思路：使用大小堆解决
注意，我们获取的中位数是有序列表中的中间的数（中间的单个元素或者两个元素均值）
解决的数据结构
我们使用两个堆来存储列表中的值，一个是大顶堆，一个是小顶堆
其中大顶堆的所有元素小于小顶堆的所有元素，并且我们需要维护大顶堆和小顶堆的大小，我们只允许大顶堆的大小等于小顶堆，或者比小顶堆小一个元素
如果是两个堆都为空的时候，先插入小顶堆，便于初始化，以便后面的元素能根据前面入堆的元素来判断应该进入哪一个堆
为什么这样的结构能解题
此时，如果我们要获取中位数，一共有两种情况
- 大顶堆大小==小顶堆元素（此时列表大小为偶数），此时，大顶堆的堆顶元素（大于大顶堆的所有元素，小于小顶堆的所有元素）就相当于列表（2n）中的第n个元素，小顶堆的堆顶元素就相当于列表中的第n+1元素，也就是只要取两个堆顶的元素除以2即可
- 大顶堆大小+1==小顶堆元素（列表大小为奇数2n+1），此时，大顶堆的元素个数为n+1，小顶堆的元素个数为n，大顶堆的堆顶元素位于列表中的第n+1位置（大于大顶堆中的所有n个元素元素，小于小顶堆的所有元素），所以大堆顶的堆顶元素就是中位数
解题代码如下
class MedianFinder {//使用两个优先级队列存储信息即可//小队列存储数值小的值，最大的放在堆顶，两个堆的数量差不能大于1（为了找中间值）//大队列存储数值大的值，最小的放在堆顶PriorityQueue<Integer> queueMin;PriorityQueue<Integer> queueMax;public MedianFinder() {queueMin=new PriorityQueue<>((a,b)->b-a);queueMax=new PriorityQueue<>((a,b)->a-b);}public void addNum(int num) {if(queueMin.isEmpty()||num<=queueMin.peek()){//如果要添加的元素小于小队列的最大值，就放入小队列queueMin.offer(num);if(queueMax.size()+1<queueMin.size()){queueMax.offer(queueMin.poll());}}else{queueMax.offer(num);//随后就是判断数量对不对if(queueMax.size()>queueMin.size()){queueMin.offer(queueMax.poll());}}}public double findMedian() {//尝试获取if(queueMin.size()>queueMax.size()){return queueMin.peek();}else{return (queueMin.peek()+queueMax.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();*/