数据流中的中位数

一、题目

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

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

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

数据范围

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

样例

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

二、思路

寻找数组中中位数的前提是数组有序，数组元素个数为奇数，中间的数字就是中位数；数组元素个数为偶数，中间两个数字相加除以2就是中位数。

但是当数组是一个动态数组的时候，如何维护数组的有序性？

最好的办法是维护两个堆，分别为一个大顶堆和一个小顶堆，大顶堆存放比中位数小的数字，小顶堆存放比中位数大的数字，其中当数组元素为奇数的时候，大顶堆的元素个数与小顶堆的元素个数不相等，我们将多出的这个数字维护在大顶堆中，这样一来，当元素个数为奇数，直接返回大顶堆的堆顶元素，当元素个数为偶数的时候，返回大顶堆和小顶堆的顶部元素的和除以2。

三、代码实现

class Solution {
public://初始化一个大根堆和一个小根堆priority_queue<int> maxheap;priority_queue<int, vector<int>, greater<int>> minheap;void insert(int num){//第一个元素放到大根堆 因为只有一个元素的时候需要返回大根堆的堆顶元素maxheap.push(num);if(minheap.size() && maxheap.top() > minheap.top()){//大根堆的元素要小于中位数 只有大根堆的堆顶元素小于中位数 小根堆的堆顶元素大于中位数 才能保证两个堆的堆顶元素接近中位数//不满足条件 交换堆顶元素int maxe = maxheap.top(), mine = minheap.top();maxheap.push(mine), minheap.push(maxe);maxheap.pop(),minheap.pop();}//保持大顶堆的元素最多只能比小顶堆多一个if(maxheap.size() > minheap.size() + 1){minheap.push(maxheap.top());maxheap.pop();}}double getMedian(){//元素总数为奇数 返回大顶堆堆顶 元素总数为偶数返回大小顶堆堆顶和除以2if((maxheap.size() + minheap.size()) & 1) return maxheap.top();else return (minheap.top() + maxheap.top()) / 2.0;}
};