点击关注公众号，干货第一时间送达
做过实时数仓的小伙伴，
应该都知道什么是数据流。
当然，熟悉Kafka的仁兄们，
对此也不陌生。
数据流，讲究的就是一个变化。
今天咱们看一道 "困难" 的题目，
来自力扣：
原题链接：
https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/description/
一、屏幕前的吴彦祖和刘亦菲们，请听题
需要实现的是一种数据结构，
能够完成对数据流的中位数，准确抓取。
该结构如下：
class MedianFinder {
public MedianFinder() {
}
public void addNum(int num) {
}
public double findMedian() {
}
}
嘶嘶嘶。。。
说实话，
是不是有点棘手？
且看小编娓娓道来。
二、解题
中位数，处于一组有序数字的中间位置。
如果我们能够把一串数字，
较小部分用大根堆存储，较大部分用小根堆存储，
那么大根堆对顶，就是较小部分最大的元素，
小根堆堆定，就是较大部分最小的元素，
那么，中位数就好求了。
举个例子：
当3流入时，判断3和大根堆堆顶大小，3 < 5，则3进入大根堆：
同时，需要判断两个堆size大小关系，
如果差值超过1，则进行调整：
于是：
继续流入6，判断 6 >3，则6进入小根堆：
接下来7，7 >3，也进入小根堆：
记得判断两个堆size大小，此时需要调整了：
数据流停止了，
如果两个堆size一样，则中位数就是两个堆顶的平均数：（5+6）/2
如果size不一样，取size较大的那个堆堆顶即可。
此方法是不是很简单
看看代码。
完整代码：
public class CodingDemo_03 {
/**
* 数据流中的中位数
*/
class MedianFinder {
//大根堆
PriorityQueue<Integer> maxHeap;
//小根堆
PriorityQueue<Integer> minHeap;
//初始化堆
public MedianFinder() {
maxHeap = new PriorityQueue<>(new MaxHeapComparator());
minHeap = new PriorityQueue<>(new MinHeapComparator());
}
//添加新数字
public void addNum(int num) {
//1，优先加入大根堆，
//每次加入，都调整两个堆，保持堆size差小于等于1
if (maxHeap.isEmpty() || num <= maxHeap.peek()){
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
modifyTwoHeap();
}
//调整两个堆
public void modifyTwoHeap(){
if (maxHeap.size() == minHeap.size() + 2){
minHeap.offer(maxHeap.poll());
}
if (minHeap.size() == maxHeap.size() + 2){
maxHeap.offer(minHeap.poll());
}
}
//查找中位数
public double findMedian() {
if (maxHeap.isEmpty()){
return -1;
}
if (maxHeap.size() == minHeap.size()){
return (double) (maxHeap.peek() + minHeap.peek())/2;
} else {
return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
}
}
}
//自定义大根堆比较器，正序排列
class MaxHeapComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
//自定义小根堆比较器，逆序排列
class MinHeapComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
}
去力扣试试：
文章转载自皮皮克克，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
