原文链接: https://leetcode-cn.com/problems/continuous-median-lcci

英文原文

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

中文题目

随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。

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

例如，

[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

通过代码

高赞题解

要求若干个数的中位数，我们其实最多只需要知道两个数（n为偶数时），在n为奇数时只需要一个数。

如何维护最中间的两个数呢？我们可以注意到，左边的是所有左边的数中的最大值，而右边的是所有右边的数中的最小值。所以我们可以用一个大根堆维护左边的最大值，同时用一个小根堆维护右边的最小值。

每次新增元素时，我们先按照大小将其放入对应的堆，再对两个堆的大小进行调整，保证左边的元素不少于右边，同时不超过右边+1。

在求中位数时，如果当前两个堆不一样大，说明总数为奇数，我们直接取左边的最大值。否则，我们取左边最大值和右边最大值的平均值。

注意：为了省去对空堆的特殊处理，预先在左边的大根堆中置入INT_MIN，在右边的小根堆中置入INT_MAX。

class MedianFinder {
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<>> right;
    
    void resize() {
        if (left.size() >= right.size() + 2) {
            right.push(left.top());
            left.pop();
        } else if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }
public:
    /** initialize your data structure here. */
    MedianFinder() {
        left.push(INT_MIN);
        right.push(INT_MAX);
    }
    
    void addNum(int num) {
        int lmax = left.top(), rmin = right.top();
        if (num <= lmax)
            left.push(num);
        else
            right.push(num);
        resize();
    }
    
    double findMedian() {
        if (left.size() == right.size())
            return ((double) left.top() + right.top()) / 2;
        else
            return left.top();
    }
};

统计信息

通过次数	提交次数	AC比率
4159	7243	57.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言