题目描述

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

思路 & 解答

用一个数字来不断统计数据流中的个数，并且创建一个最大堆，一个最小堆，如果插入的数字的个数是奇数的时候，让最小堆里面的元素个数比最大堆的个数多1，这样一来中位数就是小顶堆的堆顶，如果插入的数字的个数是偶数的时候，两个堆的元素保持一样多，中位数就是两个堆的堆顶的元素相加除以2。

代码如下：

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    private int count = 0;
    private PriorityQueue<Integer> min = new PriorityQueue<Integer>();
    private PriorityQueue<Integer> max = new PriorityQueue<Integer>(new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public void Insert(Integer num) {
        count++;
        if (count % 2 == 1) {
            // 奇数的时候，需要最小堆的元素比最大堆的元素多一个。
            // 先放到最大堆里面，然后弹出最大的
            max.offer(num);
            // 把最大的放进最小堆
            min.offer(max.poll());
        } else {
            // 放进最小堆
            min.offer(num);
            // 把最小的放进最大堆
            max.offer(min.poll());
        }
    }

    public Double GetMedian() {
        if (count % 2 == 0) {
            return (min.peek() + max.peek()) / 2.0;
        } else {
            return (double) min.peek();
        }
    }

}

C++ 代码实现如下：

class Solution {
public:
    priority_queue<int> max;
    priority_queue<int, vector<int>, greater<int> > min;
    int count = 0;

    void Insert(int num) {
        if (count % 2 == 1) {

            max.push(num);
            min.push(max.top());
            max.pop();
        } else {

            min.push(num);
            max.push(min.top());
            min.pop();
        }
        count++;
    }

    double GetMedian() {
        if (count % 2 == 1) {
            return max.top();
        } else {
            return (max.top() + min.top()) / 2.0;
        }
    }
};

空间复杂度为O(n)，取出中位数的时间复杂度为O(1)，但是每次插入的时候，由于使用了堆处理数据，每次添加数据的时间复杂度为O(nlogn)。