数据流中的中位数

题目描述

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

思路

方法一

利用堆排序,将序列分为大顶堆和小顶堆,大顶堆存放较小值,小顶堆存放较大值。当序列长度为奇数时,取大顶堆的根节点为中位数,当序列长度为偶数时,中位数是大顶堆的根节点和小顶堆的根节点的平均数。

大顶堆:根节点比其左右叶子节点的值大

小顶堆:根节点比其左右叶子节点的值小

class Solution {
    priority_queue<int, vector<int>, less<int> > p;
    priority_queue<int, vector<int>, greater<int> > q;

public:
    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();
    }
};

方法二

对于一组数据,我们可以用集合「vector arr」来存取,将 vector 排好序后,就可以很方便得到中位数了。

  1. 若vector_size为奇数,则中位数是中间的数
  2. 若vector_size为偶数,则中位数是中间两个数的平均值
class Solution {
public:
    #define SCD static_cast<double>
    vector<int> v;
    void Insert(int num)
    {
        v.push_back(num);

    }

    double GetMedian()
    { 
        sort(v.begin(), v.end());
        int sz = v.size();
        if (sz & 1) {
            return SCD(v[sz >> 1]);
        }
        else {
            return SCD(v[sz >> 1] + v[(sz - 1) >> 1]) / 2;
        }
    }

}

其他

堆排序的图解:https://www.cnblogs.com/chengxiao/p/6129630.html


   转载规则


《数据流中的中位数》 帅张 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录