剑指 Offer.41-数据流中的中位数

题目链接

问题描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

官方解法

使用大小顶堆两个进行实现，其中小顶堆需要比大顶堆多一个元素，用于处理奇数情况下的中位数求解，当需要求解中位数的时候，判断当前N为奇数还是偶数，若为奇数，直接从小顶堆弹出元素，否则，求两个堆顶元素的均值。

graph TB
    Start(开始) --> Open[判断当前两个堆的大小是否相同]
    Open --> |相同| Put[将元素放入大顶堆再从大顶堆弹出元素放入小顶堆]
    Open --> |不相同| Smart[将元素放入小顶堆再从大顶堆弹出元素放入大顶堆]

    Put --> End(结束)
    Smart --> End(结束)

代码

class MedianFinder {
    //使用两个堆进行实现
    Queue<Integer> A,B;
    /** initialize your data structure here. */
    public MedianFinder() {
        // 使用默认构造函数 构造得到是一个小顶堆
        A = new PriorityQueue<>();
        // 使用Lamda表达式传入Comparator 构造大顶堆
        B = new PriorityQueue<>((x,y)->(y-x));
    }
    
    //在添加元素时，始终保持小顶堆的元素比大顶堆高1
    public void addNum(int num) {
        // 当A,B长度不同时，此时证明数据流为奇数 需要将元素添加至B堆中
        // 但添加元素可能属于较小的一部分 所以需要先进A堆 再从A堆弹出一个元素放入B堆
        if(A.size()!=B.size()){
            A.add(num);
            B.add(A.poll());
        }else{
            //反之亦然
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size()!=B.size()?A.peek():(A.peek()+B.peek())/2.0;
    }
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。