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

题目内容

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

• 例如 $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$