力扣---剑指 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/

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

当前已经插入的数可以分为两部分，一部分是小于等于当前中位数的元素，另一部分是大于等于当前中位数的元素。

两部分的特点是差值不超过一（由中位数的定义可得）

可以想到利用两个优先队列，一个从小到大存储所有比当前中位数小的数，一个从大到小存储所有比当前中位数大的数。

此时的中位数即是两个优先队列中元素较多的那个的堆顶（或者当两者元素数量相等时，是两者堆顶元素和的二分之一）

代码如下：

class MedianFinder {
    // queue1 中的元素数量
    private int len1 = 0;
    // queue2 中的元素数量
    private int len2 = 0;
    // 存储所有比中位数小的数
    private final Queue<Integer> queue1;
    // 存储所有比中位数大的数
    private final Queue<Integer> queue2;

    /** initialize your data structure here. */
    public MedianFinder() {
        // 堆顶是最大的数。
        queue1 = new PriorityQueue<>((a, b) -> (b - a));
        // 堆顶是最小的数
        queue2 = new PriorityQueue<>((a, b) -> (a - b));
    }

    public void addNum(int num) {
        // 将 num 插入到 queue1 或 queue2 中。
        if (queue2.peek() == null || num > queue2.peek()) {
            queue2.add(num);
            len2 ++;
        } else {
            queue1.add(num);
            len1 ++;
        }
        // 维护 queue1 中的元素个数和 queue2 中的元素个数相差不超过 1 。
        while (len1 > len2 + 1) {
            queue2.add(queue1.poll());
            len1 --;
            len2 ++;
        }
        while (len2 > len1 + 1) {
            queue1.add(queue2.poll());
            len2 --;
            len1 ++;
        }
    }

    public double findMedian() {
        // 如果元素数相同，直接返回两个堆顶和的二分之一
        if (len1 == len2) {
            return (queue1.peek() + queue2.peek()) / 2.0;
        } else if (len1 > len2) {
            return queue1.peek();
        } else {
            return queue2.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */