【每日一题】4月9日题目精讲 堆

题号 NC50940
名称 Running Median
来源 《算法竞赛进阶指南》0x05
戳我进入往期每日一题汇总贴~

注:如果你在题库做题时遇到了喜欢的题目,欢迎推荐~ 点击查看详情

这算是个经(套)典(路)题了,也存在不少高端做法,比如说你想练练平衡树写法什么的都可以,这里讲解一种简单的做法——堆。

我们在之前的每日一题中给大家讲过堆这种数据结构(https://ac.nowcoder.com/discuss/390428 ),这里不再介绍。

我们可以建一个大根堆,一个小根堆,大根堆存目前数列中较小的那一半数字,小根堆存目前数列中较大的一半数字,那么中位数不是在小根堆的堆顶就是在大根堆的堆顶(根据两个堆中数字个数判断)。

每当加入一个数字的时候,我们需要判断它应该在小根堆中还是在大根堆中,然后维护两个堆的容量相同或者只相差1(如果一个堆容量大了就把它堆顶拿出来塞到另一个堆里,每次只会对一个堆顶进行一次操作)。整体复杂度是O(nlogn)的。

图片说明

代码可戳我查看~

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目4月16日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/a313fe2b12a54c3693ddfcd74a29f436
1 回复 分享
发布于 2020-04-08 11:47
https://blog.nowcoder.net/n/0d405c0c2aec4f0dbd1b13c240b0f2d2
1 回复 分享
发布于 2020-04-08 14:20
https://blog.nowcoder.net/n/71fd516c33ea44b18dbb063768e8363c
1 回复 分享
发布于 2020-04-08 16:24
https://blog.nowcoder.net/n/f7f7a3a1d5c44db8ab838ef2e2dbeaac
1 回复 分享
发布于 2020-04-08 20:21
https://blog.nowcoder.net/n/84d11852a2fc404f9a067fc6b1db91ae
1 回复 分享
发布于 2020-04-08 21:17
平衡树 https://blog.nowcoder.net/n/3534b39fbfd54ba8ac6ca41129295f5e
1 回复 分享
发布于 2020-04-09 09:31
https://blog.nowcoder.net/n/a39a0fc43364450ab5878c76266ff2d5
1 回复 分享
发布于 2020-04-10 21:12
现在题解中代码好像过不了第二组数据了
1 回复 分享
发布于 2020-07-31 10:32
https://blog.nowcoder.net/n/7a75ae3dc7aa4fc69fb46dd692f6a419
点赞 回复 分享
发布于 2020-04-08 11:00
https://blog.nowcoder.net/n/6541495619f04566ab759c2133c68b6f
点赞 回复 分享
发布于 2020-04-08 12:28
https://blog.nowcoder.net/n/5fba1fbf394d40b98b51c99d42e2732a 
点赞 回复 分享
发布于 2020-04-08 12:37
https://blog.nowcoder.net/n/5f6bc2eda9b54d8282be4553e5895f2b
点赞 回复 分享
发布于 2020-04-08 14:13
https://blog.nowcoder.net/n/8384bfb613234bc394b0096cbbd05b06
点赞 回复 分享
发布于 2020-04-08 15:21
https://blog.nowcoder.net/n/88e5d31712914f3aa043b4ee5e475efd
点赞 回复 分享
发布于 2020-04-08 17:00
https://blog.nowcoder.net/n/ffaa096119f04534bccc7aadb95e0682
点赞 回复 分享
发布于 2020-04-08 17:01
https://blog.nowcoder.net/n/43db8a0947d94df79e0afe6280d923a8
点赞 回复 分享
发布于 2020-04-08 17:05
https://blog.nowcoder.net/n/d55998c1b6ab4b0b8771a6ebcfe9f8b8
点赞 回复 分享
发布于 2020-04-08 17:25
https://blog.nowcoder.net/n/841ca0a61fba4380bb4f8a7833569eb9
点赞 回复 分享
发布于 2020-04-08 17:39
https://blog.nowcoder.net/n/055f27d3d71547ad958c671666dd3a03
点赞 回复 分享
发布于 2020-04-08 17:44
https://blog.nowcoder.net/n/ed86c878fb36416a8bcb5c7ca0b5efd4
点赞 回复 分享
发布于 2020-04-08 20:12

相关推荐

jack_miller:我给我们导员说我不在这里转正,可能没三方签了。导员说没事学校催的时候帮我想办法应付一下
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务