Leetcode 295-数据流的中位数

题解

题解参考自灵茶山艾府

通过中位数将数据分为left和right两部分

比如现在有 6 个数：1,5,6,2,3,4，要计算中位数，可以把这 6 个数从小到大排序，得到 1,2,3,4,5,6，中间 3 和 4 的平均值 3.5 就是中位数。

中位数把这 6 个数均分成了左右两部分，一边是 left=[1,2,3]，另一边是 right=[4,5,6]。我们要计算的中位数，就来自 left 中的最大值，以及 right 中的最小值。

随着 addNum 不断地添加数字，我们需要：
保证 left 的大小和 right 的大小尽量相等。规定：在有奇数个数时，left 比 right 多 1 个数。
保证 left 的所有元素都小于等于 right 的所有元素。

只要时时刻刻满足以上两个要求(left中元素<right&&left.size()==right.size())，我们就可以用 left 中的最大值以及 right 中的最小值计算中位数。

算法思想

1.如果当前 left 的大小和 right 的大小相等–>left中数字的个数需要+1
1）如果添加的数字 num 比较大，比如添加 7，那么需要把7 加到 right 中。现在 left 比 right 少 1 个数，不符合前文的规定，所以必须把 right 的最小值从 right 中去掉，添加到 left 中。如此操作后，可以保证 left 的所有元素都小于等于 right 的所有元素。
2）如果添加的数字 num 比较小，比如添加 0，那么需要把 0 加到 left 中。
这两种情况可以合并：无论 num 是大是小，都可以先把 num 加到 right 中，然后把 right 的最小值从 right 中去掉，并添加到 left 中。

算法步骤

最后，我们利用堆结构，高效地执行操作：

1.建立堆 left 是最大堆，right 是最小堆。

2.把数据流中的数据加入堆

脑子里建立如下动态的过程：为了找到添加新数据以后，数据流的中位数，我们让新数据在最大堆和最小堆中都走了一遍。而为了让最大堆的元素多 1 个，我们让从最小堆中又拿出一个元素「送回」给最大堆；

3.计算中位数

如果当前有奇数个元素，中位数是 left 的堆顶。
如果当前有偶数个元素，中位数是 left 的堆顶和 right 的堆顶的平均值。

class MedianFinder {
    private PriorityQueue<Integer> left;
    private PriorityQueue<Integer> right;

    public MedianFinder() {
        //大顶堆存最小的k个数
        left=new PriorityQueue<>((x,y)->(y-x));
        //默认小顶堆 小顶堆存最大的k个数
        right=new PriorityQueue<>();;
    }
    

    public void addNum(int num) {
        //priorityQueue的大小用size
        //left大小=right大小,新来数需要先进到right，再从right里poll出最小值给left
        if(left.size()==right.size()){
            right.offer(num);
            left.offer(right.poll());
        }else{left大小>right大小,新来数需要先进到left，再从left里poll出最大值给right
            left.offer(num);
            right.offer(left.poll());
        }
    }
    
    public double findMedian() {
        //列表数目为偶数个
        if(left.size()==right.size()) return (left.peek()+right.peek())/2.0;
        else return left.peek();
    }
}