LeetCode刷题【剑指 Offer 41】数据流中的中位数

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

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

• void addNum(int num) – 从数据流中添加一个整数到数据结构中。
• double findMedian() – 返回目前所有元素的中位数。

示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2：

输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

限制：

• 最多会对 addNum、findMedian 进行 50000 次调用。

注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/

【双薯片桶算法】又见薯片桶

本来其实看到困难题有点多想，不过回想了下之前做的这题，我的题解剑指 Offer 09. 用两个栈实现队列（简单） ， 再想想这题，好像….也没那么复杂了

借一次之前的图

我们需要的其实是一个队列。但是和之前不同的是这次是有序的，我们要从这个有序队列中取中间那个值。

这样，我们把原来的两个栈换成两个堆，一个大顶堆，一个小顶堆，那么对应这上面这个图

1. 左边一个大顶堆，堆顶是最大值
2. 右边一个小顶堆，堆顶是最小值
3. 每插入一个值的时候判断下是应该往左边的插还是往右边插，小于等于左边的最大值，就往左边插，大于等于右边的最小值，就往右边插，只要做一个判断即可
4. 插入之后对两个堆做一下平衡，保证左边堆的数量等于右边堆的数量，或者等于右边堆的数量加1，就如同上面的两个薯片桶从左往右倒一个，或者从右往左倒一个
5. 不同于之前的栈维护的队列，堆附带自动排序的属性，所以你可以认为把一个数字插入其中一个堆里的时候，可以自动将他排序到对应的正确位置，这是一个比较智能的薯片桶

代码

class MedianFinder {

    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;

    /** initialize your data structure here. */
    public MedianFinder() {
        left = new PriorityQueue<>((a,b)-> b-a);
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (left.size()==0||num<=left.peek()){
            left.offer(num);
        }else{
            right.offer(num);
        }
        if (left.size() - right.size()>1){
            right.offer(left.poll());
        }else if (right.size() > left.size()){
            left.offer(right.poll());
        }
    }
    
    public double findMedian() {
        if (left.size() == right.size()){
            return ((double) (left.peek() + right.peek()))/2;
        }else{
            return (double)left.peek();
        }
    }
}