数据流的中位数

题解思路

方法：双堆法（大顶堆 + 小顶堆）

为了高效地求解中位数，我们可以使用两个堆维护数据流的左右两半部分：

• 最大堆（left，存较小的一半）：堆顶是左半边最大值；
• 最小堆（right，存较大的一半）：堆顶是右半边最小值；

Leetcode 76.数据流的中位数-原题链接

题目内容

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 $arr = [2,3,4]$ 的中位数是 $3$ 。
• 例如 $arr = [2,3]$ 的中位数是 $(2 + 3) / 2 = 2.5$ 。

实现 $MedianFinder$ 类:

• $MedianFinder()$初始化 $MedianFinder$对象。
• $void\ addNum(int\ num)$ 将数据流中的整数 $num$添加到数据结构中。
• $double\ findMedian()$ 返回到目前为止所有元素的中位数。与实际答案相差 $10^{-5}$以内的答案将被接受。

输入描述

• 第一行输入一个整数 q，表示操作次数。
• 接下来 q 行，每行是一个操作：
  • 若为 "add x"，表示添加一个数字 x；
  • 若为 "median"，表示查询当前所有数字的中位数。

输出描述

对于每个 "median" 操作，输出一行中位数，保留 1 位小数。

样例1

输入

5
add 1
add 2
median
add 3
median

输出

1.5
2.0

说明

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示：

• $-10^5 <= num <= 10^5$
• 在调用 $findMedian$之前，数据结构中至少有一个元素
• 最多 $5 * 10^4$ 次调用 $addNum$和 $findMedian$