【剑指 Offer 】41. 数据流中的中位数

题目：41. 数据流中的中位数

思路：

写一个数据结构，实现数据流的动态添加和查找实时的中位数。（奇数个的时候中位数为A的堆顶元素）

• 静态变量：小顶堆A、大顶堆B；
• 存放数据：
  • 先判断A和B的大小：
  • 相等的话，就存在A中；
  • 不相等的话，就存在B中；
• 读取中位数：
  • 判断A和B的大小：
  • 相等就取两者堆顶元素的平均值；
  • 不相等，就弹出A的堆顶元素；

代码：

class MedianFinder {
    // 静态变量
    Queue<Integer> A,B;

    // 构造方法
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x,y)->(y-x));
    }
    
    // 添加数据
    public void addNum(int num) {
        if(A.size() == B.size()){
            B.offer(num);
            A.offer(B.poll());
        }else{
            A.offer(num);
            B.offer(A.poll());
        }
    }
    
    // 读取中位数
    public double findMedian() {
        if(A.size() == B.size()){
            return (A.peek() + B.peek())/2.0;
        }else{
            return A.peek()/1.0;
        }
    }
}