【剑指offer63 数据流中的中位数】

题目描述

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

 

创建两个堆，小顶堆存大的一部分，大顶推存小的一部分

这样两个堆顶就是最中间的树，

并维持大堆多1

 

class Solution {
public:
    priority_queue<int, vector<int>, less<int> > p; //大的在上面 存所有数据中小的一半
    priority_queue<int, vector<int>, greater<int> > q;//小的在上面 存所有数据中心大的一半
    void Insert(int num)
    {
        if(p.empty() || num <= p.top()) p.push(num);
        else q.push(num);
        //小的一半太多了  多出了一半
        if(p.size() == q.size() + 2) {
            q.push(p.top());
            p.pop();
        }
        //如果总数是奇数  把中间的元素放到小的一半  方便结果输出
        if(p.size() + 1 == q.size()) {
            p.push(q.top());
            q.pop();
        }
    }

    double GetMedian()
    { 
        return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();
    }

};