题目描述

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

思路

暴力解法：利用有序数组，来一个数就把它***已经拍好序的数组里，然后取中位数的时候直接取中间索引就可以

(看到剑指上有别的解法，之后可以考虑用大根堆，小根堆的方法进行)

代码

class Solution {
public:
    vector<int> data;
    void Insert(int num)
    {
        data.push_back(num);
        int pos=data.size()-1;  //确定num的位置
        for(int i=0;i<data.size()-1;i++)
        {
            if(data[i]>=num)
            {
                pos=i;
                break;
            }
        }
        for(int i=data.size()-1;i>pos;i--)
        {
            data[i]=data[i-1];
        }
        data[pos]=num;
    }

    double GetMedian()
    { 
        int n=data.size();
        if(n%2==1)
            return data[n/2];
        else
            return (data[n/2]+data[n/2-1])/2.0;
    }

};

方法二

采用堆的方法
一般来说，什么时候用堆，什么时候用排序呢？
如果有取数，放回，取数，放回的操作的时候，用堆更加方便(有放回的时候用堆)
这道题的策略：

• 创建一个大根堆和一个小根堆
• 第一个数放进大根堆(大根堆为空的时候放进来)
• 放的数如果小于等于大根堆的堆顶，则放进大根堆；否则，放进小根堆
• 每次放完数后，比较大小根堆的差值，差值等于2的话就进行调整(将多的那个堆的堆顶放入少的堆)
• 这样的操作会使得一半在大根堆，一半在小根堆里

取中位数：两堆大小相等，取两个堆顶的平均值；不等的话就取多的堆的堆顶

这道题明白思路之后我花了好久好久！！！
注意：这里的大根堆指的是，堆顶元素最大，在C++中，定义大根堆：priority_queue<int,vector<int>,less<int>> maxQ;</int></int>

代码

class Solution {
public:
    priority_queue<int,vector<int>,greater<int>> minQ;
    priority_queue<int,vector<int>,less<int>> maxQ;
    void Insert(int num)
    {
        if(maxQ.empty()||num<=maxQ.top())
            maxQ.push(num);
        else
            minQ.push(num);
        if(maxQ.si***Q.size()==2)
        {
            minQ.push(maxQ.top());
            maxQ.pop();
        }
        if(minQ.size()-maxQ.size()==2)
        {
            maxQ.push(minQ.top());
            minQ.pop();
        }
    }

    double GetMedian()
    {
        if(maxQ.si***Q.size())
            return (maxQ.top()+minQ.top())/2.0;
        else if(maxQ.size()>minQ.size())
            return maxQ.top();
        else
            return minQ.top();
    }

};