题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路分析
- 将插入数据存放在小顶堆和大顶堆中，我们先设定如果插入的个数为偶数个时，将此值放到右边的小顶堆中，如果为奇数时，放入到左边的大顶推中。要保证左边的大顶堆要全部小于右边的小顶堆中的值，如果此时插入个数为偶数个，那么需要插入到小顶堆中，但是此时插入的值比大顶堆中的值要小，所以就将此值放入到大顶堆中，而将大顶堆最大的值插入到小顶堆中。
- Java中的大顶堆和小顶堆可以借助优先级队列PriorityQueue，默认为小顶堆，如果要实现大顶堆，则需要反转默认排序器
测试用例
- 功能测试：从数据流中读出奇数个数字:从数据流中读出偶数个数字。
- 边界值测试：从数据流中读出0个、1个、2个数字。
Java代码
public class Offer041 {
public static void main(String[] args) {
test1();
test2();
test3();
}
int k = 11;
PriorityQueue<Integer> minQ = new PriorityQueue<Integer>(); // 小顶堆，存中位数右边的数，都大
PriorityQueue<Integer> maxQ = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// PriorityQueue默认是小顶堆，实现大顶堆，需要反转默认排序器
return o2.compareTo(o1);
}
});
private int count =0;
public void Insert(Integer num) {
count++;
if ((count & 1) == 0) {// 插入的数量为偶数 要插入右边的最小堆中
if (!maxQ.isEmpty() && num < maxQ.peek()) {// 大顶堆不为空 插入值小于左边最大堆中的数
maxQ.offer(num); //将此值插入到大顶推中
num = maxQ.poll(); // 把大顶堆中的最大值插入到小顶堆中
}
minQ.add(num);
} else {// 奇数 插入左边最大堆
if (!minQ.isEmpty() && num > minQ.peek()) {
minQ.offer(num);
num = minQ.poll();
}
maxQ.offer(num);
}
}
public Double GetMedian() {
if (count == 0)
throw new RuntimeException("error!");
double dd;
if ((count & 1) == 0) {
dd = (minQ.peek() + maxQ.peek())/2.0; // n偶数 取大顶堆和小顶堆的堆顶值／2
} else
dd = maxQ.peek(); // n为奇数 取小顶堆的最大值。
return dd;
}
private static void test1() {
}
private static void test2() {
}
private static void test3() {
}
}