41 数据流中的中位数

牛客

描述

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

示例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...

示例2
输入：[1,1,1]
返回值："1.00 1.00 1.00 "

---

实现方式有多种，排序、优先队列，等等。

综合来看，使用优先队列比较高效。使用一个大顶堆和一个小顶堆。小顶堆存放较大元素，大顶堆存放较小元素。每次元素先放大顶堆，然后再放小顶堆，保持连个堆相差最多 1 个元素。如果往存放较大元素的堆存放小于另一个堆堆顶堆元素，则放入另一个堆，然后弹出堆顶元素给较大元素的堆。可以通过两个堆堆堆顶元素得到中间元素。

插入时间复杂度 o(log n) ，获取中间元素时间复杂度 o(1)

import java.util.PriorityQueue;
public class Solution {
    
    PriorityQueue<Integer> bigNum=new PriorityQueue<>();
    PriorityQueue<Integer> smallNum=new PriorityQueue<>((i1,i2)->i2-i1);
    public void Insert(Integer num) {

        if(bigNum.size()>smallNum.size()){
            if(num>bigNum.peek()){
                bigNum.add(num);
                smallNum.add(bigNum.poll());
            } else {
                smallNum.add(num);
            }
        } else {
            if(smallNum.size()>0 && num<smallNum.peek()){
                smallNum.add(num);
                bigNum.add(smallNum.poll());
            } else {
                bigNum.add(num);
            }
            
        }
    }

    public Double GetMedian() {
        if(bigNum.size()>smallNum.size()) return (double)bigNum.peek();
        return (bigNum.peek() + smallNum.peek() )/2.0;
    }


}