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

数据流的逐个流入性质，很符合插入排序的特性。每push一个数据，就将其插入到该在的位置，使数据流有序。

class Solution {
  public:
    vector<int> stream;
    void Insert(int num) {
        stream.push_back(num);
        insertSort(stream);
    }

    double GetMedian() {
        int len = stream.size();
        if (len % 2) {
            return stream[len / 2];
        } else {
            return ((double)stream[len / 2] + (double)stream[len / 2 - 1]) / 2.0;
        }
    }
    void insertSort(vector<int>& v) {
        int len = v.size();
        if (len > 1) {
            int prior = v[len - 1];
            for (int i = 0; i < len - 1; i++) {
                if (v[i] >= prior) {
                    v.insert(v.begin() + i, prior);
                    v.pop_back();
                    break;
                }
            }
        }
    }

};