剑指41：数据流中的中位数

传送门

nowcoder
leetcode

题目描述

如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

C++ 代码 - nowcoder

/*
    对于海量数据，使用最大堆和最小堆，把数据分为[小]|[大]两个部分。
    [最大堆 | 左边最大 leftMax]、[右边最小 rightMin | 最小堆]
    保证左边和右边个数相差不大于 1，且左边大于右边。

    时间复杂度：O(logn)
        最坏情况下，插入堆和删除堆顶元素，每一次都需要 O(logn) 时间。
        找到平均值需要持续的 O(1) 时间，因为可以直接访问堆的顶部。
    空间复杂度：O(n)
*/
class Solution {
private:
    int count = 0;
    priority_queue<int, vector<int>, less<int>> left_big;       // 左边，大顶堆
    priority_queue<int, vector<int>, greater<int>> right_small; // 右边，小顶堆

public:
    void Insert(int num) {
        count += 1;
        if (count % 2 == 1) {
            // 奇数个，往后半部分加
            right_small.push(num);
            left_big.push(right_small.top());
            right_small.pop();
        } else {
            // 偶数个，往前半部分加
            left_big.push(num);
            right_small.push(left_big.top());
            left_big.pop();
        }
    }

    double GetMedian() { 
        if (count % 2 == 1) return left_big.top();
        else return (right_small.top() + left_big.top()) / 2.0;
    }
};

C++ 代码 - leetcode

/*
    对于海量数据，使用最大堆和最小堆，把数据分为[小]|[大]两个部分。

    时间复杂度：O(logn)
    空间复杂度：O(n)
*/
class MedianFinder {
private:
    int count;
    priority_queue<int,vector<int>,less<int>> left_big;
    priority_queue<int,vector<int>,greater<int>> right_small;

public:
    MedianFinder() {
        this->count = 0;
    }
    
    void addNum(int num) {
        count ++;
        if (count % 2 == 1) {
            // 奇数个，往后半部分加
            right_small.push(num);
            left_big.push(right_small.top());
            right_small.pop();
        }
        else {
            // 偶数个，往前半部分加
            left_big.push(num);
            right_small.push(left_big.top());
            left_big.pop();
        }
    }
    
    double findMedian() {
        if (count % 2 == 1) return left_big.top();
        else return (right_small.top() + left_big.top()) / 2.0;
    }
};

/*
	思路同上，写法略不同
*/
class MedianFinder {
private:
    priority_queue<int, vector<int>, less<int>> large;    // 大顶堆
    priority_queue<int, vector<int>, greater<int>> small; // 小顶堆

public:
    MedianFinder() {
    }
    
    void addNum(int num) {
        if (large.size() <= small.size()) {
            small.push(num);
            large.push(small.top());
            small.pop();
        } else {
            large.push(num);
            small.push(large.top());
            large.pop();
        }
    }
    
    double findMedian() {
        if (large.size() < small.size()) {
            return small.top();
        } else if (large.size() > small.size()) {
            return large.top();
        } 
        return (large.top() + small.top()) / 2.0; 
    }
};