法1：暴力
用vector arr来存取。如果对vector排好序，则很容易求出中位数

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;
        }
    }

};

法2：堆排序

可以参考：剑指 Offer 41. 数据流中的中位数 | 吴师兄学算法

则根据中位数可以把数组分为如下三段: [0 ... median - 1], [median], [median + 1 ... arr.size() - 1]，即[中位数的左边，中位数，中位数的右边]

用两个堆，一个大根一个小根堆，那么很明显，求中位数可以是：

• 大根堆或者小根堆的第一个（奇数个数），此处规定小根堆的堆顶。
• 大根堆或者小根堆加和/2（偶数个数）

PS：可以参考NO29的关于堆的介绍。

堆维护的细节：

• 要保证数据平均分配到两个堆中，因此两个堆中数据的数目之差不能超过1
• 要保证最大堆中里的所有数据都要小于最小堆中的数据

为了让每次新增一个数据到两个堆之后，都能使得从大顶堆到小顶堆是一个递增有序的数组，我们可以采取如下的操作：

1. 如果两堆长度相等，即长度都为 n 时，新数据先加入到大顶堆中，然后再把大顶堆的堆顶元素取出，放入到小顶堆中。
2. 当两堆长度不相等，即小顶堆长度为 n，大顶堆长度为 n – 1，新数据先加入到小顶堆中，然后再把小顶堆的堆顶元素取出，放入到大顶堆中。

#include <queue>
#include <vector>
class Solution {
public:
    std::priority_queue<int> max_q; 
    std::priority_queue<int, vector<int>, greater<>> min_q; // 小顶堆 维护右边区间
    int cnt = 0;

    void Insert(int num) {
        cnt++;
        if(max_q.size() == min_q.size()){
            max_q.push(num);
            min_q.push(max_q.top());
            max_q.pop();
        }else{
            min_q.push(num);
            max_q.push(min_q.top());
            min_q.pop();
        }
    }

    double GetMedian() { 
        if(cnt % 2 == 0){
            return double(max_q.top() + min_q.top()) / 2.0;
        }else{
            return double(min_q.top());
        }
    }

};