源自《剑指offer》第63题
问题描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解题思路
求中位数，避免不了需要用一个容器将流入的数据保存起来，那么选择什么容器比较合适呢？
1）数组
- 最简单的容器。
- 如果是未排序的数组，找中位数的方法采用快排的
Partition()。因此，插入时间复杂度是，而找中位数的时间复杂度是
。
- 如果是排序的数组，由于是流式数据，适合使用插入排序。因此，插入的时间复杂度是
，而找中位数的时间复杂度是
2）链表
- 由于数组使用插入排序，每次都需要进行大量的位移操作和扩容操作，故此可使用链表取代。
- 排序的链表，插入的时间复杂度还是
3）二叉搜索树
- 使用二叉搜索树，可以将插入的时间复杂度降至
；而找到中位数的时间复杂度是
- 但二叉搜索树有可能退化成一个链表，此时插入的时间复杂度是
4）AVL
- 将普通的二叉搜索树改进成平衡二叉树（AVL），再将左右子树深度只差1个单位，这样插入数据的时间复杂度是
- 由于 AVL 实现很复杂，面试过程不可能手写。
5）一个大顶堆+一个小顶堆【推荐】
- tips：题目只要中位数，而中位数左边和右边是否有序不重要（思想类似于「求序列中第k个大的数字」）
- 核心思想：中位数左边的数据（左边数据特点是都不大于中位数）保存在大顶堆中，中位数右边的数据（右边数据特点是都不小于中位数）保存在小顶堆中。【关键在于保持两个堆保存的数据个数相等或只差一个】
- 根据堆的插入，插入数据的时间复杂度是
- 大/小顶堆的实现可以使用
java.util.PriorityQueue
代码实现
以下是实现「第五种方案：一个大顶堆+一个小顶堆」的详细思想描述以及代码。
关键点：
- 中位数左边的数据保存在大顶堆；中位数右边的数据保存在小顶堆中。
- 始终保持两个堆保存的数据个数相等或者只差一个。
实现思路：
- 当输入数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中；
- 当输入数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中；
- 取中位数的时候，如果当输入数目为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当输入数目为奇数，显然是取小顶堆的根节点
代码实现：
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
// 大顶堆, PriorityQueue默认是大顶堆
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
// 小顶堆
private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
// 输入数据的总数
private int total_count = 0;
public void Insert(Integer num) {
//个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中
if(total_count % 2 == 0){
maxHeap.offer(num);
int max = maxHeap.poll();
minHeap.offer(max);
}else{
//个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中
minHeap.offer(num);
int min = minHeap.poll();
maxHeap.offer(min);
}
total_count++;
}
public Double GetMedian() {
if (total_count%2 == 0)
return (minHeap.peek() + maxHeap.peek()) / 2.0;
else
return (double)minHeap.peek();
}
}
参考
[1] 数据流中的中位数 - 剑指 Offer 学习心得 - 极客学院Wiki
[2] 【面试题63-数据流中的中位数】 · fossi
网友评论