源自《剑指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