【LeetCode】剑指 Offer(22)
创始人
2024-06-01 23:32:29
0次

目录

题目:剑指 Offer 41. 数据流中的中位数 - 力扣(Leetcode)

题目的接口:

解题思路:

代码:

过啦!!!

写在最后:


题目:剑指 Offer 41. 数据流中的中位数 - 力扣(Leetcode)

题目的接口:

class MedianFinder {
public:/** initialize your data structure here. */MedianFinder() {}void addNum(int num) {}double findMedian() {}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

解题思路:

我的思路是:

通过优先级队列维护一个大堆,一个小堆;

输入数据的时候:

1. 如果两个堆size相同,先进大堆,大堆top再进小堆,维持大堆比小堆小;

2. 如果小堆size大于大堆,先进小堆,小堆top再进大堆,维持大堆比小堆小。

例:

现在两个堆大小相同,

所以2进大堆:

根据我们的思路,

再进小堆:

现在小堆比大堆大,

我们先让3进小堆:

然后,让小堆的top

再进大堆:

现在大堆和小堆又一样大了,

所以,4先进大堆:

然后让大堆的top

再进小堆:

 

通过观察上面的图解,我们可以清楚的观察到,

大堆和小堆实现了一个动态的平衡状态,

也让中位数的求解变成只需要观察他们的堆顶即可。

查找中位数的时候:

1. 如果小堆size大于大堆,返回小堆堆顶;

2. 如果两个堆size相等,返回两个堆堆顶的值*0.5(中位数)。

代码:

class MedianFinder {
public://建一个大堆priority_queue, less> max_q;//建一个小堆priority_queue, greater> min_q;MedianFinder() {}void addNum(int num) {//如果两个堆size相等if(max_q.size() == min_q.size()){//先进大堆,大堆top再进小堆,维持大堆比小堆小max_q.push(num);min_q.push(max_q.top());max_q.pop();}else//如果小堆size大于大堆{//先进小堆,小堆top再进大堆,维持大堆比小堆小min_q.push(num);max_q.push(min_q.top());min_q.pop();}}double findMedian() {//如果小堆size大于大堆,返回小堆堆顶//如果两个堆size相等,返回两个堆堆顶的值*0.5(中位数)return max_q.size() < min_q.size() ? min_q.top() : (max_q.top() + min_q.top()) * 0.5;}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

过啦!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。

相关内容

热门资讯

存储芯片巨头的好日子何时结束 ... 摩根士丹利最新报告指出,旧存储芯片行业的前景被低估。曾经因供需失衡而获得高额利润的旧存储芯片现在正处...
国足开场2分钟落后 邵佳一眉头... 点击加载图片直播吧11月17日讯 国足开场2分钟丢球,0-1落后巴林,镜头给到眉头紧锁的邵佳一。国字...
小米:相关内容纯属虚构,警惕虚... 小米旗下微博账号“小米辟谣”于11月17日发布声明,指出近期有不法分子冒充“小米汽车”发送诈骗短信,...
最差密码榜单公布 123456... 网络安全公司 NordPass 发布了《2026 年最常用密码 Top 200》报告,指出“1234...
2岁孩子生命最后11天依然努力... 25岁的妈妈将患有罕见病的儿子兜兜送进了长沙的“雏菊之家”安宁病房。她陪伴儿子度过了最后11天,并每...
13岁少年被控杀害5岁男童案 ... 一名13岁少年因妹妹被邻居5岁男童撒沙而心生怨恨,将男童带至桥上推下水致其溺亡。此案引起了媒体的广泛...
全球顶尖科学家加速回流中国 风... 全球顶尖科学家纷纷选择离开美国,转向中国任职。2026年初,莱斯大学90后斯隆奖得主汪淏田全职加盟同...
APEC工商领导人峰会今天聚焦... 11月17日,来自亚太经合组织21个经济体及英国、法国、德国、瑞士等13个域外经济体的2000多位政...
雷军APEC发言 具身智能潜力... 11月17日,小米CEO雷军在2026年APEC工商领导人峰会上表示,具身智能机器人的潜力超过汽车,...
俄罗斯记者惊呼在深圳谁还用现金... 11月17日,今日俄罗斯国际通讯社记者德米特里·加夫里洛夫在接受采访时分享了他的深圳体验。他提到,刚...
雷军:智能机器人产业潜力超汽车... 11月17日,在2026年亚太经合组织工商领导人峰会上,小米CEO雷军介绍了公司在AI、智能制造和机...
保研举报成风,这不只是“坏人变... 保研举报成风,这不只是“坏人变小了” 制度留操作空间。高校保研季举报成风:这不是学生坏,是制度留了太...
广东01年医护女孩为00年闺蜜... 据河南广播电视台小莉帮忙,广东一位01年的女孩,亲自为自己00年的闺蜜接生。她们的缘分有多深?女孩称...
广东网友为迎接APEC会议周有... 11月14日,2026年APEC领导人会议周新闻中心举办了广东省、深圳市专场中外媒体吹风会。这是20...
动车插座在头顶被吐槽像在打吊瓶... 近日,有网友在社交平台发帖分享自己的乘车经历:乘坐D2928次动车组时,发现车厢内的充电插座安装在顶...
万斯称与特朗普无分歧 一致反对... JD·万斯周一表示,他与总统唐纳德·特朗普在伊朗战争问题上完全一致。此前,他曾将共和党在中期选举中的...
痛风人群这4种饮品要少喝 咖啡... 很多尿酸高、痛风人群都知道啤酒、果汁会升高尿酸,那么有没有什么饮料对尿酸“很友好”,甚至还能降低痛风...
医生辟谣左侧睡根本不伤心:正常... 11月17日,经常朝左睡对心脏的影响引发关注。从解剖学角度看,心脏虽然位于胸腔偏左,但它并非孤零零地...
96岁奶奶扒着车窗含泪送孙女返... 近日,湖南,假期快要结束,孙女准备返程。96岁的奶奶扒着车窗,眼里满是不舍。一句有空常回家看看,戳中...
人民日报:从《持械入宋》火爆看... 有能够让行业内外普遍认可的作品出现,是一种新文艺类型成熟的重要标志。正是因为“家里家外”系列、《盛夏...