题目描述

有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。
[要求]
1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)
每行有一个整数opt表示操作类型
若opt=1，则接下来有一个整数N表示将N加入到结构中。
若opt=2，则表示询问当前所有数的中位数

方法一 暴力检索

解题思路

最简单的方法就是存储所有的整数，需要查询中位数时通过排序得到需要的结果。

代码示例（超时）

class Solution {
public:
    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    // 存储数据
    vector<double> store;

    vector<double> flowmedian(vector<vector<int> >& operations) {
        // write code here
        vector<double> res;
        for(auto & v : operations) {
            if(v[0] == 1)
                addNum(v[1]);
            else
                res.push_back(findMedian());
        }
        return res;
    }

    void addNum(int num) {
        // 朴素地把num加入vector中
        store.push_back(num);
    }

    double findMedian() {
        sort(store.begin(), store.end());
        // 根据排序后的数组寻找中位数
        int n = store.size();
        // 边界情况
        if(n == 0)
            return -1;
        return (n & 1 ? store[n / 2] : (store[n / 2 - 1] + store[n / 2]) * 0.5);
    }
};

复杂度分析

• 时间复杂度：插入操作需要，查询中位数操作因为需要排序复杂度为，所以时间复杂度为。查询中位数时间复杂度远大于题目要求，故因超时未通过。
• 空间复杂度：需要存储个数，故复杂度为

方法二 插入查找

解题思路

此方法为方法一的优化版本。方法一每次查询操作都对数组进行排序操作；本方法每次插入时保持数组的有序性，在查询时仅需要查询数组的中间位置一个或两个数即可。这样通过增加插入时的时间复杂度来减少查询时的时间复杂度。

代码示例

class Solution {
public:
    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    // 存储数据
    vector<double> store;

    vector<double> flowmedian(vector<vector<int> >& operations) {
        // write code here
        vector<double> res;
        for(auto & v : operations) {
            if(v[0] == 1)
                addNum(v[1]);
            else
                res.push_back(findMedian());
        }
        return res;
    }

    void addNum(int num) {
        // 通过二分法插入num，保证vector的有序性
        if (store.empty())
            store.push_back(num);
        else
            store.insert(lower_bound(store.begin(), store.end(), num), num);
    }

    double findMedian() {
        // 因为数组有序，因此只需取出中间位置的数
        int n = store.size();
        // 边界情况
        if(n == 0)
            return -1;
        return (n & 1 ? store[n / 2] : (store[n / 2 - 1] + store[n / 2]) * 0.5);
    }
};

复杂度分析

• 时间复杂度：插入操作时需要二分查找，复杂度为，查询中位数操作只需要取出数组中间位置的数，复杂度为，时间复杂度符合要求。
• 空间复杂度：需要存储个数，故复杂度为

方法三 双堆

解题思路

根据题目要求的时间复杂度很容易想到树或者堆等数据结构。与方法二类似，我们在插入元素时保持数据有序，借助堆可以进一步优化时间复杂度（插入后的数据移动部分的时间复杂度）。
因为关心的是中位数的值，因此我们可以建立一个大顶堆lo和一个小顶堆hi，分别存储数据较小的一半和较大的一半，即

• lo的大小为N/2（N为偶数）或N+1/2（N为奇数）
• hi的大小为N/2（N为偶数）或N-1/2（N为奇数）
  

这样，我们可以根据lo和hi的堆顶元素找到中位数的值，即findMedian()函数的实现：

• lo的大小等于hi的大小时，N为偶数，中位数为lo和hi堆顶元素的平均值
• lo的大小大于hi的大小时，N为奇数，中位数为lo的堆顶元素

实现addNum()函数时，遵循以下规则：

• lo的大小等于hi的大小时，N为偶数，需向lo添加一个元素。实现方法：将新元素num插入至hi，再将hi堆顶元素插入至lo
• lo的大小大于hi的大小时，N为奇数，需向hi添加一个元素。实现方法：将新元素num插入至lo，再将llo堆顶元素插入至hi

这样，可以保证hi中所有元素大于lo中所有元素，以保证中位数的查询。

代码示例

class Solution {
public:
    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    // 大顶堆，存储较小的那一半数
    priority_queue<int> lo;
    // 小顶堆，存储较大的那一半数
    priority_queue<int, vector<int>, greater<int>> hi;

    vector<double> flowmedian(vector<vector<int> >& operations) {
        // write code here
        vector<double> res;
        for(auto & v : operations) {
            if(v[0] == 1)
                addNum(v[1]);
            else
                res.push_back(findMedian());
        }
        return res;
    }

    void addNum(int num) {
        // 此时需要将num添加入hi中以保证堆大小的平衡
        if (lo.size() > hi.size()) {
            // 保证插入到hi中的元素大于lo中所有元素
            lo.emplace(num);
            hi.emplace(lo.top());
            lo.pop();
        }
        // 此时需要将num添加入lo中以保证堆大小的平衡
        else {
            // 保证插入到lo中的元素小于hi中所有元素
            hi.emplace(num);
            lo.emplace(hi.top());
            hi.pop();
        }
    }

    double findMedian() {
        // 边界情况
        if(lo.size() == 0)
            return -1;
        // 根据堆顶元素得到中位数
        if(hi.size() == lo.size())
            return (hi.top() + lo.top()) / 2.0;
        else
            return lo.top();
    }
};

复杂度分析

• 时间复杂度：向大根堆和小根堆插入数据的时间复杂度为，查询中位数操作需要取出堆顶元素，复杂度为，时间复杂度符合要求。
• 空间复杂度：需要用堆存储个数，故复杂度为