JZ41 数据流中的中位数
JZ41 数据流中的中位数
描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用 Insert() 方法读取数据流，使用 GetMedian() 方法获取当前读取数据的中位数。
数据范围：数据流中数个数满足 1 ≤ n ≤ 1000 ，大小满足 1≤ val ≤1000
进阶： 空间复杂度 O(n) ， 时间复杂度 O(nlogn)
示例1
输入：
[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 "
// 说明：数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...
示例2
输入：
[1,1,1]
返回值：
"1.00 1.00 1.00 "
解析
本题的目的就是求一个一直在变化的数组（即读取的数据流）的中位数。求中位数需要先让数组有序，所以肯定少不了排序。可以很快想到的一种解决方法是，每次读取新数据到数组中后，都进行一次排序以保证数组有序，然后按照中位数的定义获取中位数即可。
不过每次读取新数据后都进行排序，时间复杂度取决于排序算法的时间复杂度，且每读进一个数就要执行一次排序，时间复杂度甚至可能达到 O(n^3)，写出来也非常膈应。
所以需要寻找另外的方法，以降低时间复杂度。可以注意到，若能一直保持数组有序，则每次都是在有序数组中插入新数据。这样问题就转换成了：在有序数组中插入新数据，同时保持数组有序，应对这个问题的算法想必就很容易想到了：二分查找插入法。
代码清单
import java.util.*;
public class Solution {
private ArrayList list = new ArrayList<>();
public void Insert(Integer num) {
int start = 0;
int end = list.size()-1;
int mid = 0;
if(list.isEmpty()){
list.add(num);
return;
}
// 需要这个 =，当 start 与 end 重合时，再进行一次判断
// 若当前数比插入数小，则插入的位置应该是 start+1；反之 end-1 结束循环，插入位置就是 start
while(start <= end){
mid = start+(end-start)/2;
if(num < list.get(mid))
end = mid - 1 ;
else
start = mid + 1 ;
}
// 是 start 而不是 mid
list.add(start,num);
}
public Double GetMedian() {
int size = list.size();
double median;
if(size % 2 == 1)
median = (double)list.get(size/2);
else
median = (double)(list.get(size/2)+list.get((size/2)-1))/2;
return median;
}
}
其中，Insert() 方法就是二分查找插入的方法，维护 list 数组的有序；然后 GetMedian() 方法可以直接按中位数定义获取数组的中位数。
二分查找插入不是什么很难的算法，甚至属于简单算法，不过还是折磨到了我。
写的时候遇到了两个问题：
- 最后插入的位置应该是
start而不是mid。因为 mid 是 start 和 end 的平均数，所以遇到除不尽的情况只会靠向 start（ int 型取舍）。如在[1,3,4]中插入 2，mid 最终会变成 0，即将 2 插入到 1 前面，这显然是大错特错。 - 循环条件
start <= end中的=是非常关键的。当 start 与 end 重合时，此时的 mid 等于 start，会再进行一次判断，若当前数比插入数小，则插入的下标应该是 start+1；反之 start 不变， end-1 结束循环，插入下标就是 start。如在[1,3,4]中插入 2，start 与 end 都是 0 时，由于 1 < 2，start 变成 1，最后插入的下标就是 1；又如在在[3,3,4]中插入 2，start 一直是 0 ，end 会收缩为 -1 结束循环，所以插入下标就是 0。
时间复杂度为二分查找插入的 O(logn)，和挪动数据的 O(n)。简单的算法，也容易犯错。
总结
本题有最简单解法，但我肯定不会这样做。不过二分查找插入的方法也算不上最好，本题的最优解应该是使用大根堆与小根堆，只需使用堆维护中位数，不需要挪动数据，时间复杂度为 O(logn)。不过我开摆了。