如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[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(); */
