源自《剑指offer》第63题

问题描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解题思路

求中位数，避免不了需要用一个容器将流入的数据保存起来，那么选择什么容器比较合适呢？

1）数组

最简单的容器。
如果是未排序的数组，找中位数的方法采用快排的 Partition()。因此，插入时间复杂度是 $O(1)$ ，而找中位数的时间复杂度是 $O(k*log(n))$ 。
如果是排序的数组，由于是流式数据，适合使用插入排序。因此，插入的时间复杂度是 $O(n)$ ，而找中位数的时间复杂度是 $O(1)$

2）链表

由于数组使用插入排序，每次都需要进行大量的位移操作和扩容操作，故此可使用链表取代。
排序的链表，插入的时间复杂度还是 $O(n)$ ，找中位数的时间复杂度是 $O(n)$

3）二叉搜索树

使用二叉搜索树，可以将插入的时间复杂度降至 $O(log(n))$ ；而找到中位数的时间复杂度是 $O(n)$
但二叉搜索树有可能退化成一个链表，此时插入的时间复杂度是 $O(n)$ 。

4）AVL

将普通的二叉搜索树改进成平衡二叉树（AVL），再将左右子树深度只差1个单位，这样插入数据的时间复杂度是 $O(log(n))$ ，找到中位数的时间复杂度是 $O(1)$ 。
由于 AVL 实现很复杂，面试过程不可能手写。

5）一个大顶堆+一个小顶堆【推荐】

tips：题目只要中位数，而中位数左边和右边是否有序不重要（思想类似于「求序列中第k个大的数字」）
核心思想：中位数左边的数据（左边数据特点是都不大于中位数）保存在大顶堆中，中位数右边的数据（右边数据特点是都不小于中位数）保存在小顶堆中。【关键在于保持两个堆保存的数据个数相等或只差一个】
根据堆的插入，插入数据的时间复杂度是 $O(log(n))$ 。而中位数肯定在两个堆的堆顶元素中，找到中位数的时间复杂度是 $O(1)$ 。
大/小顶堆的实现可以使用 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

【流式数据】求数据流中的中位数

【流式数据】求数据流中的中位数

问题描述

解题思路

代码实现

参考