题目详情

有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。
[要求]

1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)

每行有一个整数opt表示操作类型
若opt=1，则接下来有一个整数N表示将N加入到结构中。
若opt=2，则表示询问当前所有数的中位数

示例1
输入
复制
[[1,5],[2],[1,3],[2],[1,6],[2],[1,7],[2]]
返回值
复制
[5,4,5,5.5]
说明
第一次查询时结构内的数为：5
第二次查询时结构内的数为：3 5
第二次查询时结构内的数为：3 5 6
第二次查询时结构内的数为：3 5 6 7

示例2
输入
复制
[[2],[1,1],[2]]
返回值
复制
[-1,1]

分析

• 题目要求复杂度为log(n) ，且整个过程是个动态(不断插入元素)的过程，可想而知只有二叉树之类的方法可以达到这个复杂度。
• 中位数即某个能将所有数根据大小关系划分为左右两半的数，只要能够不断的维护好这两部分的数，中位数就能在O(1)的时间内求得
  • 如果n % 2 == 0即偶数个元素, 则median = max(left) + min(right) / 2
  • 否则n % 2 == 1即奇数个元素，则median = max(left) or min(right)

方法1 堆

• 使用两个堆来分别维护left和right。当插入一个数的时候，朴素的想法是分别与max(left)和min(right)进行比较，之后插入到对应的堆中，再平衡两个堆的大小。但这种方法需要多个if/else，一种优雅的方法是让数据在两个堆中流动一遍。

class Solution {
public:
    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    priority_queue<int, vector<int>, less<int>> lo;
    priority_queue<int, vector<int>, greater<int>> hi;

    vector<double> flowmedian(vector<vector<int> >& operations) {
        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) {
        # 数据流动
        lo.push(num);
        hi.push(lo.top());
        lo.pop();
        # 总是让size(lo) >= size(hi)
        if (lo.size() < hi.size()) {
            lo.push(hi.top());
            hi.pop();
        }
    }

    double findMedian() {
        if (!lo.size())
            return -1;
        # 总数量为偶数，取两数的一半
        if (lo.size() == hi.size())
            return (double)(lo.top() + hi.top()) / 2;
        else
            return lo.top();
    }
};

方法二 平衡数

• 该方法非常简单粗暴，当插入的数比当前中位数大时，说明中位数会后移，反之则前移。
• 这里的树并不是必须的，只不过如果用数组来组织元素的话复杂度会变成O(n)

class Solution {
public:
    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    multiset<int> s;
    multiset<int>::iterator mid;

    vector<double> flowmedian(vector<vector<int> >& operations) {
        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) {
        int size = s.size();
        s.insert(num);
        if (size == 0)
            mid = s.begin();
        else {
            # 比较中位数和新插入数的大小，进行相应的前移/后移
            if (num < *mid)
                mid = (size & 1) ? prev(mid) : mid;
            else
                mid = (size & 1) ? mid : next(mid);
        }
    }

    double findMedian() {
        if (!s.size()) return -1;
        if (s.size() & 1)
            return *mid;
        else {
            return (*mid + *next(mid)) / 2.0;
        }
    }

};