【剑指 offer】数据流中的中位数

2019-05-02  本文已影响0人  七月初一_3679

1、题目描述

如何得到一个数据流中的中位数?

如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

样例

输入:1, 2, 3, 4
输出:1,1.5,2,2.5

解释:每当数据流读入一个数据,就进行一次判断并输出当前的中位数。

2、问题描述:

3、问题关键:

4、C++代码:

class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    void insert(int num){
        max_heap.push(num);
        if (min_heap.size()) {
            int tmp = min_heap.top();
            if (tmp < max_heap.top()) {//如果小根堆堆顶元素小于大根堆,那么就交换堆顶元素。保证小根堆元素大于大根堆元素。
                min_heap.pop();
                min_heap.push(max_heap.top());
                max_heap.pop();
                max_heap.push(tmp);
            }
        }
        if (max_heap.size() > min_heap.size() + 1) {//如果大根堆元素比小根堆元素大2,那么将堆顶元素放入小根堆。
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }
    double getMedian(){//数量量相同那么就是堆顶元素平均数,否则是大根堆堆顶元素为中位数。
        if (min_heap.size() == max_heap.size() && min_heap.size()) 
            return (min_heap.top() + max_heap.top()) / 2.0;
        else 
            return max_heap.top();
    }
};
上一篇 下一篇

猜你喜欢

热点阅读