【牛客】BM48数据流中的中位数

数据流中的中位数-牛客网"https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1?tpId=295&tqId=23457&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj"

描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

数据范围：数据流中数个数满足 1≤n≤1000 ，大小满足 val≤1000

进阶： 空间复杂度 O(n) ， 时间复杂度 O(nlogn)

示例1

输入：
[5,2,3,4,1,6,7,0,8]
返回值：
"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明：
数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...     

题解

//小根堆，存储大于等于middle的部分
PriorityQueue<Integer> min_q = new PriorityQueue<>();
//大根堆，存储小于middle的部分
PriorityQueue<Integer> max_q = new PriorityQueue<>(Collections.reverseOrder());
public void Insert(Integer num) {
    Double middle = GetMedian();
    //判断新的数放在哪个堆
    if(num >= middle){
        min_q.offer(num);
    }else{
        max_q.offer(num);
    }
    //调整两个堆大小
    if(max_q.size() > min_q.size()){
        min_q.offer(max_q.poll());
    }else if(min_q.size() > max_q.size()+1){
        max_q.offer(min_q.poll());
    }
}

public Double GetMedian() {
    if(min_q.size() == 0){
        return 0.0;
    }
    if(max_q.size() == min_q.size()){
        Double a = Double.valueOf(max_q.peek());
        Double b = Double.valueOf(min_q.peek());
        return (a+b)/2.0;
    }else{
        Double b = Double.valueOf(min_q.peek());
        return b;
    }
}