题解 | #数据流中的中位数# 基于官方题解的逻辑整理

数据流中的中位数

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

#include <functional>
#include <queue>
#include <vector>
class Solution {
public:
    priority_queue<int> left;
    priority_queue<int,vector<int>,greater<int>> right;
    void Insert(int num) {
        right.push(num);
        // 此时代码缺少“排序”的逻辑,所以出问题,如何用两个优先队列实现排序?
        // 排序
        left.push(right.top());
        right.pop();
        right.push(left.top());
        left.pop();

        if(right.size() > left.size()+1){
            left.push(right.top());
            right.pop();
        }
    }

    double GetMedian() { 
        if(right.size() > left.size()){
            return right.top();
        }else{
            return (double)((double)left.top() + (double)right.top())/2;
        }
    }

};

基于牛客官方的题解,但是感觉自己理解起来比较困难,在此整理思路:

首先是通过两个“优先队列”的数据结构实现寻找中位数的逻辑,具体实现时需要考虑的问题有:

1、如何正确地实现两个优先队列的逻辑功能。

2、如何在两个优先队列的基础上判断返回值的逻辑。

首先考虑第一个逻辑问题:这两个队列希望实现的逻辑是一个保存了现有输入的较小的一部分并且能返回该部分的最大值(为了中位数),另外一个保存另外(较大)的一部分并返回其中的最小值。那么如何实现呢?

我想到的是针对新加入的一个数,它可能会导致两个队列的变化,即针对一个新的输入如何调整两个队列,使得他们各自实现各自的逻辑功能?如果新加入的值属于较大的这一部分,那么直接加入right即可,如果是较小的那一部分,需要将其和left部分的最大值位置替换。所以有了排序那部分代码。这样就成功维持了两个优先队列。

其次考虑第二个问题:中位数的判断和输入个数是奇数还是偶数有关,所以这个逻辑需要在代码的某些属性上体现出来,自然地想到两个队列包含的元素个数。

具体实现就是通过维持两个队列的个数实现,如果总数是奇数,一定会有一个队列的元素个数比另外一个多的情况出现,如果是偶数,根据中位数的概念应该是排序后的中间两个数取平均。

基于这种逻辑那么元素个数的逻辑就清晰起来了,即偶数时两个队列元素个数相同,奇数的时候一个并另外一个多1。具体实现就是通过判断两个队列的元素个数执行对应的调整代码。

全部评论

相关推荐

练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
06-18 13:28
已编辑
门头沟学院 Web前端
爱睡觉的冰箱哥:《给予你300的工资》,阴的没边了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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