295. 数据流的中位数

题目

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-median-from-data-stream
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路与代码

思路一，quickSort（TLE）

这个方法就不多做介绍了，插入时间复杂度为O(1)，排序时间复杂度为O(nlogn)，检索结果时间复杂度为O(1)

class MedianFinder {
    vector<int> result;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        result.push_back(num);
    }

    double findMedian() {
        sort(result.begin(),result.end());
        return (double)(result[(int)(result.size()-1)/2]+result[(int)result.size()/2])/2;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

思路二，insertionSort

此思路与快排思路几乎一样，但insertionSort的复杂度会更适合这道题目。我们从始至终维护好已有元素的有序性，这样在插入新元素时，用二分法找到插入位置的时间复杂度为O(logn)，将元素插入到该位置的时间复杂度为O(n)，检索结果的时间复杂度为O(1)

class MedianFinder {
    vector<int> nums;
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        if(nums.empty()) nums.push_back(num);
        else nums.insert(lower_bound(nums.begin(),nums.end(),num),num);
    }

    double findMedian() {
        int n=nums.size();
        return n&1?nums[n/2]:(nums[n/2-1]+nums[n/2])*0.5;
    }
};

思路三，两个堆

我们并不需要排序整个数组。我只需要知道中间值是多少就行...唔，中间值，那就是堆呗！
我们可维护两个堆：

最大堆，存储输入元素中较小的那一半，堆顶为较小那一半的最大值
最小堆，存储输入元素中较大的那一半，堆顶为较大那一半的最小值
但我们还需要满足条件：
两个堆是接***衡的（堆的大小要一致，如果是奇数个元素，则堆大小差只为1）

由此，我们的挑战变成了，如何平衡这两个堆。以下是算法思路：

两个优先队列（优先队列其实就是堆嘛）
- 最大堆lo存储较小那一半的元素
- 最小堆hi存储较大那一半的元素
最大堆的元素数量允许比最小堆的元素数量大一
- 如果元素数量为奇数，则答案为最大堆的顶部元素
- 如果元素数量为偶数，则答案为两个堆的顶部元素的一半
当添加一个元素num进堆时
- 添加num到lo中。添加后，我们必须对两个堆进行平衡操作，于是我们移除最大堆的最大值，将其分配给hi
- hi在被分配新元素后，持有的元素可能会比lo持有的元素多。如果真是这样，我们再将最小堆hi的最小值分配给最大堆lo。

class MedianFinder {
    priority_queue<int> lo;//最大堆
    priority_queue<int, vector<int>, greater<int>> hi;//最小堆
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }

    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top());
        lo.pop();
        if(lo.size()<hi.size()){
            lo.push(hi.top());
            hi.pop();
        }
    }

    double findMedian() {
        return lo.size()>hi.size()?lo.top():(double)(lo.top()+hi.top())/2;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */