如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
- 功能测试（从数据流中读出奇数个数字；从数据流中读出偶数个数字）。
- 边界值测试（从数据流中读出0个、1个、2个数字）
- 考察应聘者对时间复杂度的分析能力。
- 考察应聘者对数据结构的理解程度。应聘者只有对各个常用数据结构容器的特点非常了解，知道他们的优缺点及适用场景，才能找出最优的解法。
其实我们要解决的这样一个问题：选择数据容器，不容的数据容器的插入和查询时间复杂度对于这道题是不一样的。总结如下，具体的实现思路可以参考《剑指Offer》：
| 数据结构 | 插入的时间复杂度 | 得到中位数的时间复杂度 |
|---|---|---|
| 没有排序的数组 | O(1) | O(n) 利用了Partition函数 |
| 排序的数组 | O(n) | O(1) |
| 排序的链表 | O(n) | O(1) |
| 二叉搜索树 | 平均O(logn),最差O(n) | 平均O(logn),最差O(n) |
| AVL树 | O(logn) | O(1) |
| 大顶堆和小顶堆 | O(logn) | O(1) |
我们这里以大顶堆和小顶堆解题，具体的实现思路如下：
将整个数据容器分为两部分，要求左右数据的数目之差不能超过1。左右部分不要求排序，但左边的需要都比右边的小即可。所以左边用大顶堆表示，右边用小顶堆表示。
为了实现平衡分配，可以在数据的总数目是偶数时把数据插入最小堆，否则插入最大堆。
在要把数据插入最小堆的时候，如果该数比最大堆的数还要小，那么需要先插入最大堆，把最大堆的最大值拿出来出入到最小堆。反之亦然。
这里用优先级队列来模拟大顶堆和小顶堆。
/**
* 数据流中的中位数
*
* @Author rex
* 2018/8/24
*/
public class Solution {
/**
* 大顶堆，存储左半边元素 （需重写比较器）
**/
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
/**
* 小顶堆，存储右半边元素，并且右半边元素都大于左半边
**/
private PriorityQueue<Integer> right = new PriorityQueue<>();
/**
* 当前数据流读入的元素个数，用于判断奇偶
**/
private int count = 0;
/**
* 读取数据流
*
* @param num
*/
public void insert(Integer num) {
// 为了实现平衡分配，可以在数据的总数目是偶数时把数据插入最小堆，否则插入最大堆
if ((count & 1) == 0) {
// 在要把数据插入最小堆的时候，如果该数比最大堆的数还要小
// 那么需要先插入最大堆，把最大堆的最大值拿出来出入到最小堆
// 反之亦然
left.add(num);
right.add(left.poll());
} else {
right.add(num);
left.add(right.poll());
}
count++;
}
/**
* 获取当前读取数据的中位数
*
* @return
*/
public Double getMedian() {
if ((count & 1) == 0) {
return (left.peek() + right.peek()) / 2.0;
} else {
return (double)right.peek();
}
}
}见参考解题。