说明

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如：

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。

double findMedian() - 返回目前所有元素的中位数。

输入格式

第一行，一个整数$n$，表示列表中元素个数

第二行，$n$个数的列表

输出格式

返回目前所有元素的中位数

样例

2
1 2

1.5

3
1 2 3

2

进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？

如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

数据范围

0<$n$<10000

0<$num$<10000

来源

LeetCode 295