|
有如下一道题：数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
数据范围：数据流中数个数满足 1≤n≤1000 ，大小满足 1≤val≤1000 。
示例
输入：[5,2,3,4,1,6,7,0,8]
返回值："5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
本题的意思是给你一个不断添加新元素的序列，动态的维护这个序列的中位数。我们知道求中位数需要排序，那么本题的朴素做法就是每添加进一个新元素就对数组重新排一次序，再求中位数，插入时间复杂度为O(1)，求中位数时间复杂度为O(nlogn)，显然这样的做法并非最优。但我们能很快想到一个优化的方法，添加新元素再排序，这不就是插入排序吗？所以可以使用插排的思想，动态的让序列有序，插入时间复杂度为找到插入位置O(n)+插入时移动数组O(n)，求中位数时间复杂度为O(1)。插排的插入过程我们又知道可以利用二分优化，所以插入时间复杂度进一步降低到O(logn)+O(n)。
但此时仍不是最优解！我们知道要想动态维护一个有序的序列，堆排序是首选。但是此处由于求中位数时需要取出序列最中间的1个或2个元素，而堆只能取出堆顶的元素，对于求中位数来说很不方便，那么此题就无法用堆求解了吗？其实并非如此，一个堆不够，我们就用两个堆：
对于一个序列，其中位数将序列分为了两个子序列：开始 ~ x，y ~ 末尾，左子序列的值均小于等于中位数，右子序列的值均大于等于中位数，这两个部分都分别有序且合并后仍整体有序。中位数的计算则与两个子序列的长度有关：如果两个序列等长，如：1 2、3 4，则中位数等于（2+3）/2，即（x+y）/2，而由于两个子序列均有序（默认为升序），x即为左子序列的最大值，y即为右子序列的最小值，也就是当两个序列等长时，中位数等于（左子序列的最大值+右子序列的最小值）/2；若左子序列更长，且长度仅比右子序列大1时，如：1 2 3、4 5，则中位数直接等于3即x的值；同理，右子序列更长，且长度仅比左子序列大1时，中位数直接等于y的值，最终我们就得到了子序列长度与中位数的关系，总结如下：
- 两个序列等长，中位数等于（左边序列的最大值+右边序列的最小值）/2；
- 左边序列长度-右边序列长度=1，中位数等于左边序列的最大值；
- 右边序列长度-左边序列长度=1，中位数等于右边序列的最小值。
这时就可以使用一个堆来动态维护左边序列的最大值，另一个堆来维护右边序列的最小值。注意到实际2、3点我们只要选一个实现就可以了，因为不可能左边序列更长同时又右边序列更长，在编程时先预设好让哪个序列更长，下面的示例代码中选择让右边序列更长。另外插入时要思考清楚，堆确保了左右子序列分别有序，但没有确保它们整体有序，需要你在插入时维护，例如下面就是一个错误的插入方式：数据：5 2 1 7，左子序列插入5，左子序列长度为1，右子序列长度为0，左长度大于右长度，为确保右子序列更长，将左子序列的最大值移入右子序列：null、5，左子序列插入2，左右子序列长度相等均为1，不用移动：2、5，左子序列插入数据1，左子序列长度为2，右子序列长度为1，左长度大于右长度，将左子序列的最大值移入右子序列：1、2 5，左子序列插入数据7，左右子序列长度相等均为2，不用移动：1 7、2 5，插入完成，但是计算序列的中位数时发现这样得到的结果为（7+2）/2=4.5，而实际结果应为（2+5）/2=3.5，这样插入无法保证整体有序，那么该情况下正确的插入为数据先插入到右子序列，然后右子序列的最小值移入到左子序列，后面的判断不变，也就是左子序列的数据是有序地从右子序列中取出的，而右子序列作为堆结构本身就是有序的，自然整体还是有序的。示例代码如下所示：
import java.util.*;
public class Solution {
PriorityQueue<Integer> min = new PriorityQueue<>();
//大顶堆，元素数值较小
PriorityQueue<Integer> max = new PriorityQueue<>((a, b)->b.compareTo(a));
public void Insert(Integer num) {
min.add(num);
max.add(min.poll());
if(max.size()>min.size())
min.add(max.poll());
}
public Double GetMedian() {
if(min.size()>max.size()){
return (double)min.peek();
}else{
return (double)(min.peek()+max.peek())/2;
}
}
}
|