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

方法：插入排序

具体步骤：

1、当数组为空时，直接插入数据；当数组不为空时，遍历数组寻找合适的位置进行插入；这样得到的数组就行排序好的。 2、获取数据流的中位数。

时间复杂度：o(n)。

空间复杂度：o(n)。

class Solution {
  public:
    vector<int> res;
    void Insert(int num) {
	  	//数组为空时，直接插入数据
        if (res.empty())
            res.push_back(num);
	  	//数组不为空时，需要找对位置插入数据
        else {
            int i = 0;
            while (num >= res[i] && i < res.size()) {
                i++;
            }
            res.insert(res.begin() + i, num);
        }
    }

    double GetMedian() {
        int length = res.size();
        if (length % 2 == 1)
            return res[length / 2];
        else {
            double num1 = res[length / 2];
            double num2 = res[length / 2 - 1];
            return (num1 + num2) / 2;
        }
    }
};

上述方法插入时，寻找位置可以使用二分查找，而不是直接遍历，能够降低时间复杂度。