题目描述

如何得到一个数据流中的中位数？

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

数据范围

数据流中读入的数据总数 [1,1000]

输入：1, 2, 3, 4
输出：1,1.5,2,2.5
解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

方法一：堆 O(nlogn)

我们可以利用大根堆和小根堆的性质，创建这样两个堆，用大根堆去存储中位数往左的数，用小根堆去存储中位数往右的数。这两个堆一定满足以下两个条件（大根堆中的所有数都要小于等于小根堆中的数）：

如果数的个数 n 为奇数，则大根堆需要存 n/2 + 1 个数，小根堆需要存 n/2 个数。

如果数的个数 n 为偶数，则大根堆需要存 n/2 个数，小根堆需要存 n/2 个数。

放入元素 x ：

如果两个堆元素数量相同，则先把 x 放入右边的小根堆，再从小根堆堆顶拿出一个元素放到左边的大根堆，这样保证左边堆的数值都小于右边堆的数值。

如果两个堆元素数量不同即左边堆的数大于右边堆的数，则先把 x 放入左边的大根堆，再从大根堆堆顶拿出一个元素放到右边的小根堆，这样保证右边堆的数值都大于左边堆的数值。拿出中位数：

如果两个堆元素数量不同，则返回左边堆的堆顶。因为左边堆是大根堆，所以堆顶是该堆中值最大的，由于两个堆元素数量不同即元素总数是奇数，故中位数是取中间的值。为了能快速取出中位数，大根堆的数量就要比小根堆的数量大 1 ，这多出的那个 1 就是中位数。

假设要求 [1,2,3,4,5] 的中位数，则左边的大根堆中存 [1,2,3] ，右边的小根堆中存 [4,5] ，而大根堆堆顶 3 就是中位数。

如果两个堆元素数量相同，则返回左边堆的堆顶和右边堆的堆顶的平均值。同理，由于两个堆元素数量相同，则中位数是中间两个数的平均数，所以将大根堆堆顶与小根堆堆顶取平均值。

假设要求 [1,2,3,4] 的中位数，则左边的大根堆中存 [1,2] ，右边的小根堆存 [3,4] ，而平均数就是大根堆的堆顶 2 和小根堆的堆顶 3 求平均值得 2.5 。

class Solution {
public:
    priority_queue<int, vector<int>> maxHeap;    //大根堆
    priority_queue<int, vector<int>, greater<int>> minHeap;   //小根堆
    void insert(int num) {
        if (maxHeap.size() == minHeap.size())
        {
            minHeap.push(num);
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
        else
        {
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }
    double getMedian() {
        if (maxHeap.size() == minHeap.size())
            return (maxHeap.top() + minHeap.top()) * 1.0 / 2;
        else
            return maxHeap.top() * 1.0;
    }
};

欢迎大家在评论区交流~