题解 | #数据流中的中位数#

描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
示例1
输入：
[5,2,3,4,1,6,7,0,8]
返回值：
"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明：
数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...

class Solution {
    vector<int> nums;  // 存储插入的数据
    int N = 0;         // 记录插入数据个数
public:
    void Insert(int num) {
        nums.push_back(num);
        int i = N-1;
        while (i >= 0 && nums[i] > num) {  // 类似于插入排序
            nums[i+1] = nums[i];           // 大于则后移
            --i;
        }
        nums[i+1] = num;
        ++N;
    }

    double GetMedian() { 
        return N%2 ? nums[N/2] : (nums[N/2]+nums[N/2-1])/2.0; // 返回中位数
    }
};