题解 | #数据流中的中位数#

数据流中的中位数

https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

#include <queue>
#include <vector>
class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, std::greater<int>> min_heap;

    void Insert(int num) {
        // 大顶堆为空或大顶堆堆顶大于插入元素
        if (max_heap.empty() || max_heap.top() > num) {
            max_heap.push(num);
        } else {
            min_heap.push(num);
        }

        int min_size = min_heap.size();
        int max_size = max_heap.size();

        // 检查堆中元素是否相等或者数量相差1
        if (max_size - min_size > 1) {
            int max_top = max_heap.top();
            max_heap.pop();
            min_heap.push(max_top);
        } else if (max_size < min_size) {
            int min_top = min_heap.top();
            min_heap.pop();

            max_heap.push(min_top);
        }
    }

    double GetMedian() {
        if (max_heap.size() == min_heap.size()) {
            return (max_heap.top() + min_heap.top()) /2.0;
        }
        return (double)max_heap.top();
    }

};

堆是首选思路

由于要求中位数

因此, 需要用到两个堆 大顶堆,小顶堆,

同一个元素,如果满足大顶对的条件, 优先插入到大顶堆上面,

否则, 插入小顶堆上;

然后检查两个堆是否平衡,如果不平衡, 将其弹出, 插入小顶堆上;

note_coding 文章被收录于专栏

记录自己的解题思路, 欢迎评价

全部评论

相关推荐

牛客83265014...:完了,连现在都没开始面,13号投的是不是晚了
秋招的第一个offer,...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务