数据流中的中位数

方法一：vector中的sort函数

class Solution {
public:
    vector<int> v;
    //将数据流输入到容器vector中存储
    void Insert(int num) {
        v.push_back(num);
    }
    //由于vector自带排序函数sort，所以可以用vector自带的sort函数进行排序
    //排好序后判断一下容器中的元素个数是奇数还是偶数
    //如果是奇数，就返回下标为n/2的位置的值
    //如果是偶数，就返回下标为n/2加上n/2-1位置的值的平均值
    double GetMedian() { 
       sort(v.begin(),v.end());
       int n=v.size();
       if(n%2!=0){
          return v[n/2];
       }else{
          return 1.0*(v[n/2]+v[n/2-1])/2;
       }
    }

};

方法二:插入排序，用到vector中的lower_bounnd函数，和insert函数

思路：因为对于方法一可知每次vector中的都已经是有序了，只要在原先有序的序列中插入新的元素即可，不需要重新排序

class Solution {
public:
    vector<int> v;
    //将数据流输入到容器vector中存储
    void Insert(int num) {
        if(v.empty()){
           v.push_back(num);
        }else{
            auto it=lower_bound(v.begin(),v.end(),num);
            v.insert(it,num);
        }
    }
    //由于vector自带排序函数sort，所以可以用vector自带的sort函数进行排序
    //排好序后判断一下容器中的元素个数是奇数还是偶数
    //如果是奇数，就返回下标为n/2的位置的值
    //如果是偶数，就返回下标为n/2加上n/2-1位置的值的平均值
    double GetMedian() { 
       sort(v.begin(),v.end());
       int n=v.size();
       if(n%2!=0){
          return v[n/2];
       }else{
          return 1.0*(v[n/2]+v[n/2-1])/2;
       }
    }

};

方法三：堆排序（优先队列）

思路：由于对于插入排序每次还是要遍历整个数组，可以用堆排序

代码：

class Solution {
public:
    //由于对于有序的数列的中位数：
    //如果将序列分为三部分：[0,mid-1],mid,[mid+1,n-1]
   //那么如果左区间的长度等于右区间的长度，那么就取左区间的最大值和右区间的最小值，求出两者的平均值就是序列的中位数
   //否则如果左区间的长度比右区间的长度长1，那么就表示左区间的最大值就是中位数
   //否则如果右区间的长度与左区间的长度长1，那么就表示右区间的最小值就是中位数

   //所以可以设置一个大根堆和一个小根堆
   //大根堆可以用STL中的优先队列：只需要写数据类型，因为默认为大根堆
   //小根堆要说明数据类型、容器、比较方式
    priority_queue<int>min;
    priority_queue<int,vector<int>,greater<int>>max;
    void Insert(int num) {
        //进行堆排序：
        //先将元素插入大根堆中，再将大根堆的堆顶元素出堆进入小根堆中，就可以实现堆排序
        //因为大根堆的堆顶是大根堆中最大的元素，小根堆中的堆顶就是小根堆中的最小的元素
       min.push(num);
       max.push(min.top());
       min.pop();
       //由于后面默认当为奇数的时候，大根堆的堆顶就是中位数，所以可以发现大根堆的元素个数肯定是大于等于小根堆的元素的个数的，所以在进行堆排序的时候需要维护元素个数差
       //当发现大根堆的元素比小根堆的元素少时，就让小根堆的堆顶放入大根堆中，因为对于中位数放在小根堆和大根堆都可以
       if(min.size()<max.size()){
          min.push(max.top());
          max.pop();
       }
    }
    
    double GetMedian() { 
        //如果是奇数，就返回大根堆的堆顶即为中位数
       if(min.size()>max.size()){
            return (double)min.top();
       }else{
        //如果是偶数，就返回小根堆的堆顶和大根堆的堆顶的平均值
        return (double)(min.top()+max.top())/2;
       }
    }

};