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

class Solution {
public:
    // 记录输入流
    vector<int> val;
    void Insert(int num) {
        if(val.empty()) 
            val.push_back(num); // val中没有数据，直接加入
        // val中有数据，需要插入排序
        else{
            int i = 0;
            for(; i < val.size(); ++i){
                if(num <= val[i]) break;
            }
            val.insert(val.begin() + i, num);   // 插入排序
        }
    }

    double GetMedian() { 
        int n = val.size();
        // 奇数个数字
        if(n % 2 == 1){
            return double(val[n / 2]);
        }
        // 偶数个数字
        else{
            // 注意不能写成 double a = (val[n / 2] + val[n / 2 - 1]) / 2；这种形式，
            // (val[n / 2] + val[n / 2 - 1]) / 2; 会先进行整型int的除法（自动抹掉小数），然后把结果转成double，
            double a = val[n / 2];
            double b = val[n / 2 - 1];
            return (a + b) / 2;
        }
    }
};

vector容器中有插入排序方法，val.insert(iterator, element)，这是我没想到的~~~