题解 | #随时找到数据流的中位数#

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;
    }
};