算法通关村14关 | 数据流中位数问题

1. 数据流中位数问题

题目

 LeetCode295: 中位数是有序列表中间的数，如果列表长度是偶数，中位数是中间两个数的平均值，

例如:[2,3,4]的中位数是3，

[2,3]中位数是（2+3）/ 2= 2.5

设计一个数据结构：

void addNum(int num) 从数据流中添加一个整数到数据结构中

double findMedian()-返回目前所有元素的中位数。

思路

用大顶堆+小顶堆来求解，

小顶堆：存储所有元素中较大的一半，堆顶存储的是其中最小的数

大顶堆：存储所有元素中较小的一半，堆顶存储的是其中最大的数

相当于把元素分为两半，我们计算中位数，只需要小顶堆和大顶堆的根节点即可。

以[1,2,3,4,5]为例，砍成两半后为[1,2]和[3,4,5]我们只要能快速找到2和3即可。

下面看看使用两个堆是怎么变化的

1. 添加1，进入minHeap中，中位数是1，
2. 添加2，比民Heap堆顶元素1大，进入minHeap中，同时minHeap中元素超过了所有元素的总和的一半，所以要平衡一下，分一个给maxHeap，中位数是(1+2)/2=1.5.
3. 添加3，它比minHeap堆顶的元素2大，进入minHeap，中位数为2。
4. 添加4，比minHeap堆顶的元素2大，进入minHeap，，同时minHeap中元素超过了所有元素的总和的一半，所以要平衡一下，分一个给maxHeap，中位数是(2+3)/2=2.5.
5. 添加5，它比minHeap堆顶的元素3大，进入minHeap，中位数为3。

代码

public class MediaFinder {//小顶堆存储的是比较大的元素，堆顶是其中的最小值PriorityQueue<Integer> minHeap;//大顶堆存储的是比较大的元素，堆顶是其中的最大值PriorityQueue<Integer> maxHeap;public MediaFinder(){this.minHeap = new PriorityQueue<Integer>();this.maxHeap = new PriorityQueue<Integer>((a, b) -> (b - a));}public void addNum(int num){//小顶堆存储的是比较大的元素，num比较大元素中最小的还大，所以，进入minHeapif (minHeap.isEmpty() || num > minHeap.peek()){minHeap.offer(num);//如果minHeap比maxHeap多两个元素，就平衡if (minHeap.size() - maxHeap.size() > 1){maxHeap.offer(minHeap.poll());}}else {maxHeap.offer(num);//这样可以保证多的那个元素一定在minHeap中if (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;}}
}