剑指Offer(六十三):数据流中的中位数

2018年2月1日10:42:16 5 5,565 °C
摘要

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

剑指Offer(六十三):数据流中的中位数

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

这道题的解法有很多,文本使用最大和最小实现。

主要思想:

最大堆 | 最小堆

我们将数据分为两部分,位于左边最大堆的数据比右边最小堆的数据要小,左、右两边内部的数据没有排序,也可以根据左边最大的数及右边最小的数得到中位数。

接下来考虑用最大堆和最小堆实现的一些细节。

首先要保证数据平均分配到两个堆中,因此两个堆中数据的数目之差不能超过1.为了实现平均分配,可以在数据的总数目是偶数时把新数据插入到最小堆中,否则插入到最大堆中。

此外,还要保证最大堆中所有数据小于最小堆中数据。所以,新传入的数据需要先和最大堆的最大值或者最小堆中的最小值进行比较。以总数目为偶数为例,按照我们制定的规则,新的数据会被插入到最小堆中,但是在这之前,我们需要判断这个数据和最大堆中的最大值谁更大,如果最大堆中的数据比较大,那么我们就需要把当前数据插入最大堆,然后弹出新的最大值,再插入到最小堆中。由于最终插入到最小堆的数字是原最大堆中最大的数字,这样就保证了最小堆中所有数字都大于最大堆的数字。

2、代码

下面代码中,我们基于stl中的函数push_heap、pop_heap以及vector实现堆。比较仿函数less和greater分别用来实现最大堆和最小堆。

C++:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:5   其中:访客  3   博主  2

    • avatar 一轮红日 来自天朝的朋友 谷歌浏览器 Windows 10 福建省 铁通 1

      博主,这些都是研究生期间学习的吗,因为我有打算考研,但是计算机基础不扎实

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 辽宁省沈阳市 联通GSM/WCDMA/LTE共用出口

          @一轮红日 嗯,研究生期间学习的,我本科非计算机。

            • avatar 一轮红日 来自天朝的朋友 谷歌浏览器 Windows 10 福建省 铁通 1

              @Jack Cui 谢谢

          • avatar 真实荒言 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 北京宽带通电信技术有限公司 1

            博主好人,感谢

              • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 辽宁省沈阳市 联通GSM/WCDMA/LTE共用出口

                @真实荒言 感谢支持