题解主要思想:采用二分法将新数加入到已排好序的数组中(算法复杂度O(logN)),然后通过下标给出中位数(算法复杂度O(1)),代码如下
class Solution { public: /** * the medians * @param operations int整型vector<vector<>> ops * @return double浮点型vector */ // 采用二分法将一个数快速插入到一个排序数组中o(logN) void addNumtoMedianHolder(vector<int>& medianHolder, int num) { int n1 = 0; int n2; int index; if (medianHolder.empty())medianHolder.push_back(num); else { n2 = medianHolder.size() - 1; if (num >= medianHolder[n2])medianHolder.push_back(num); else if (num <= medianHolder[0])medianHolder.insert(medianHolder.begin(), num); else { while (n2 - n1 > 1) { index = (n1 + n2) / 2; if (num > medianHolder[index]) n1 = index; else if (num < medianHolder[index]) n2 = index; else break; } medianHolder.insert(medianHolder.begin() + n2, num); } } } double getMedian(vector<int> medianHolder) { if (medianHolder.empty())return -1; int n = medianHolder.size(); if (n % 2 == 0)return (double)(medianHolder[n / 2 - 1] + medianHolder[n / 2]) / 2; else return medianHolder[n / 2]; } vector<double> flowmedian(vector<vector<int> >& operations) { // write code here double median; vector<double> medians; vector<int> temp; vector<int> medianHolder; int nn = operations.size(); for (int i = 0; i < nn; i++) { temp = operations[i]; if (temp[0] == 1) { addNumtoMedianHolder(medianHolder, temp[1]); } else { median = getMedian(medianHolder); medians.push_back(median); } } return medians; } };