一道简约而不简单的算法题——数据流的中位数 | 附动画解析
作者 | 程序员小吴
转载自微信公众号（ID:CXYxiaowu）
题目来源于 LeetCode 上第 295 号问题：数据流的中位数。难度级别为 Hard，目前通过率为 33.5% 。
题目描述
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
输入：
输出：
题目解析
这道题给我们一个数据流，让我们找出中位数。对于数据流这种动态（流动）的数据，如果使用数组存储，那么每次新进来一个数据都进行排序的话，效率很低。
处理动态数据来说一般使用的数据结构是栈、队列、二叉树、堆。
本题中，我们使用 堆 这种数据结构。
首先将数据分为两部分，位于 上边最大堆 的数据要比 下边最小堆 的数据都要小。
为了保证将数据平均分配到两个堆中，在动态的操作的过程中两个堆中数据的数目之差不能超过 1。
为了保证 最大堆中的所有数据都小于最小堆中的数据，在操作过程中，新添加进去的数据需要先和最大堆的最大值或者最小堆中的最小值进行比较。
动画描述
代码实现
class MedianFinder {
public PriorityQueue<Integer> minheap, maxheap;
public MedianFinder() {
//维护较大的元素的最小堆
maxheap = new PriorityQueue<Integer>(Collections.reverseOrder());
//维护较小元素的最大堆
minheap = new PriorityQueue<Integer>();
}
// Adds a number into the data structure.
public void addNum(int num) {
maxheap.add(num);
minheap.add(maxheap.poll());
if (maxheap.size() < minheap.size()) {
maxheap.add(minheap.poll());
}
}
// Returns the median of current data stream
public double findMedian() {
if (maxheap.size() == minheap.size()) {
return (maxheap.peek() + minheap.peek()) * 0.5;
} else {
return maxheap.peek();
}
}
};（本文为AI科技大本营转载文章，转载请联系原作者）
◆
实习生招募
◆
推荐阅读：
详解爱奇艺ZoomAI视频增强技术的应用 | 公开课笔记
DOTA2人机决战：2:0！OpenAI击败世界冠军OG
Python的10个“秘籍”，这些技术专家全都告诉你了
从头构建恶性肿瘤检测网络 | 100行Python代码理解深度学习关键概念
马云再谈 996：真正的 996 与被剥削无关
漫画：图的 “最短路径” 问题 | 技术头条
从 0 到管理 200 人，这位程序员是如何做到的？ | 程序员有话说
4000万假币流入波场, 发生在凌晨的BTT假币攻击事件始末及细节披露
程序员为什么都爱穿冲锋衣？（最全总结）
❤点击“阅读原文”，查看更多精彩文章。
相关文章：
HBase安装与命令行操作
2019独角兽企业重金招聘Python工程师标准>>> HBase简介 基于Hadoop的NoSql数据库，适合存储半结构化、非结构化的稀疏数据，提供增删改查能力。因为其底层是hdfs，所以具有存储海量数据，高容错，高可用等特点&a…
zip/unzip 命令
zip 命令 功能说明：压缩文件。语 法：zip [-AcdDfFghjJKlLmoqrSTuvVwXyz$][-b <工作目录>][-ll][-n <字尾字符串>][-t <日期时间>][-<压缩效率>][压缩文件][文件...][-i <范本样式>][-x <范本样式>]补充说明…
《App架构师实践指南》：移动开发的进阶指南
文章主要内容：什么是 app 架构师这本书主要内容读完感受什么是 App 架构师成为“架构师”是许多程序员的梦想，当然也包括我，在工作的几年里，我见过很多架构师，他们在设计某个大型系统时具备很大的话语权，可…
FoveaBox：目标检测新纪元，无Anchor时代来临 | 技术头条
作者 | CV君转载自我爱计算机视觉（ID:aicvml）目标检测的任务是“分类”并从图像中“定位”出物体，但长久以来，该领域的工作大多是这样：生成可能包含目标的区域，然后在该区域提取特征并分类。显然࿰…
【Ubuntu】安装中文输入法、终端不支持中文的解决方法
一、中文输入法安装 1、安装汉语语言包 sudo apt install fcitx sudo apt install language-pack-zh-hans2、安装google拼音输入法 sudo apt install fcitx-googlepinyin安装完毕后，重启或者退出登陆 3、安装sun-pinyin输入法 sudo apt install fcitx-sunpinyi…
CCNA 第一章 网际互联
第一章 网际互联 路由器知识点： 1、默认时，路由器不转发任何广播包和组播包。 2、路由器使用逻辑地址，逻辑地址在网络层的包头中，用来决定将包转发到的下一跳路由器。 3、路由器可以使用管理员创建的访问表来控制被允许进入或流出…
【Cmake】执行cmake命令时报错：No XSLT processor found
一、问题描述 在ubuntu中，在生成Doc(文档)中，执行cmake命令时报错：No XSLT processor found 二、原因查找 google该错误信息，原因是确实ubuntu中没有安装 xsltproc 三、解决方法 安装 xsltproc sudo apt install xsltproc四…
一张“黑洞”需要拍两年？有了它或许就不会让大家等那么久了
只闻其名，不见其形，从小听到大的”黑洞“，终于让我们在有生之年见到了它的真容，只能说幽暗的宇宙美丽也调皮，长久以来人类关于黑洞的探索，在这一刻终于得到影像印证。相信很多人心中都有一个疑惑࿰…
如何在一场面试中展现你对Python的coding能力？| 技术头条
点击上方↑↑↑蓝字关注我们~作者 | wLsq 来源 | Python数据科学（ID:PyDataScience）如果你已经通过了招聘人员的电话面试，那么下面正是该展现你代码能力的时候了。无论是练习，作业，还是现场白板面试，这都是…
Django web : CSRF verification failed. Request aborted.
错误标题：CSRF verification failed. Request aborted. 错误描述： HelpReason given for failure:CSRF cookie not set.In general, this can occur when there is a genuine Cross Site Request Forgery, or when Djangos CSRF mechanism has not been …
分享一个PC端六格密码输入框写法
如图。我们一般做商城类的项目不免会用到支付密码输入框，我研究了下并决定发上来，也当作是自己成长路上的一点小小的记录。本次介绍的是基于vue的项目 html： <template><div classam_payPwd :id"ids_${id}"><input …
【数据库】sqlite中PRAGMA命令说明
关于sqlite中PRAGMA的说明网上已经有很多了，这里不再复制粘贴，只把内容最全的网址连接记录一下： 官网说明（英文）：https://sqlite.org/pragma.html 中文翻译，参见博客：https://www.i…
思科交换机各类型中字母的意思？
24TC-L中各字母的意思分别指? 24TT-L中第二个T的意思? 2960和2960G的区别？基中G是什麽意思? F0/1和G0/1区别？ 24代表是24个网络接口 第一个T表示TX，也就是所谓RJ-45的类型（指这个24个接口都是RJ-45，若是P的话&#…
医生还未失业，IBM Watson已跌入深渊 | 极客头条
点击上方↑↑↑蓝字关注我们~作者 | Eliza Strickland译者 | Major编辑 | 琥珀出品 | AI 科技大本营（公众号ID：rgznai100）导语：2011 年，Jeopardy! 挑战赛的成功，让外界看到 IBM 的人工智能给医学带来的革命…
【Qt】Qt容器总结
目录 一、容器类1、顺序容器2、关联容器二、Qt容器特点三、迭代器1、Jave样式的迭代器（效率略低）2、SLT样式的迭代器注意： 由于Qt的容器是写时复制的，因此非const访问器从本质上讲更加昂贵， 因为它们必须首先检查是否需要复制基础数据（并在必要时进行复制）。 因此，在Qt…
Java5线程并发库之保障变量的原子性操作
为什么80%的码农都做不了架构师？>>> java.util.concurrent.atomic 首先我们看java.util.concurrent.atomic包，它主要是提供一些为各种数据类型变量提供原子性操作的类。 AtomicInteger 比如我们来看AtomicInteger类，大家在写程序…
EIGRP OSFP 利用NULL0接口防止路由环路 Loopback Null0接口揭秘
在EIGRP中，只要发生总结就会在路由表中自动产生一条指向NULL0的路由条目，这条路由的直接意思是：匹配这条路由的数据包会被路由器丢掉。它的目的是为了避免在某些情况下产生路由环路。 以第三四学期的中文书P86中的图4-15为例做个说明…
【C++】C++11 STL算法(一)：非修改序列操作（Non-modifying sequence operations）
目录一、all_of、any_of、none_of：1、官方说明2、谓词3、STL算法对谓词的说明4、谓词的五种模式5、all_of （C 11）6、any_of （C 11）7、none_of（C 11）8、官方demo：二、for_each1、原型…
Python openpyxl 之 Excel 文档简单操作
背景：生活中常常因日常工作，在记录统计方面需频繁处理较多 Excel 表格，这部分工作虽可由人工完成，但这样会显得有些繁琐且可能存在偏差，遂闲时查阅了是否有相关基于python处理Excel表格的学习文档，后获知这…
售价910元！周志华等人英文新书《演化学习》出炉！
点击上方↑↑↑蓝字关注我们~整理 | 琥珀出品 | AI 科技大本营（公众号ID：rgznai100）关于人工智能教育，从学生培养方案，到课程设置、教材，甚至是授课老师，全国各大高校正探索一条新道路。先是从去…
linux 查看 文档 不显示注释 命令
原文：http://www.weiruoyu.cn/?p661 最近发现一个很好的命令，就是linux 查看 文档 不显示注释 的命令[rootlocalhost ha.d]# cat ha.cf |grep -v ^# logfile /var/log/ha-log 转载于:https://blog.51cto.com/weiruoyu/705840
【C++】C++11 STL算法(二)：修改序列的操作（Modifying sequence operations）
目录一、copy、copy_if1、原型：2、说明：3、官方demo二、copy_n1、原型：2、说明：3、官方demo三、copy_backward1、原型：1、说明：1、官方demo四、move1、原型：2、说明：3、官方demo五、…
ECharts测量图,功率图
/*** 测量图，功率图1，仪表盘*/ mainpage.prototype.initEcharsGLT1 function(oneJZ){ //if(myChartGLT1 null && myChartGLT1 ! "" && myChartGLT1 ! undefined) {myChartGLT1.dispose(); //每次加载之前清除之前的echar…
北京智源人工智能研究院启动“智源学者计划”，与旷视发布首个智源联合实验室
4月16日，北京智源人工智能研究院与中国人工智能领军企业旷视召开“智源学者计划暨联合实验室发布会”。北京市科委副主任张光连，海淀区委常委、副区长李俊杰，以及来自科技部、北京市科委、海淀区人民政府、朝阳区人民政府、中关村管委会&…
配置隧道模式的IPSec.×××
一、拓扑及IP配置 二、配置清单 R1#show run Building configuration... Current configuration : 1449 bytes ! upgrade fpd auto version 12.4 service timestamps debug datetime msec service timestamps log datetime msec no service password-encryption ! hostname R1 …
【C++】C++11 STL算法(三)：分隔操作（Partitioning operations）、排序操作（Sorting operations）
目录分隔操作（Partitioning operations）一、is_partitioned1、原型：2、说明：3、官网demo二、partition1、原型：2、说明：3、官方demo三、partition_copy1、原型：2、说明：3、官方demo四…
浪潮发布重磅产品“元脑”，专注AI全栈能力输出
整理 | 一一出品 | AI科技大本营（ID:rgznai100）4月16日，以“智慧凝聚”为题的IPF2019浪潮云数据中心合作伙伴大会在上海举办。大会重点聚焦浪潮“智慧计算”战略，以AI计算力和创新力，联接、承载、赋能合作伙伴。为了布…
React+Redux+中间件
MVVM是Model-View-ViewModel的缩写。mvvm是一种设计思想。Model 层代表数据模型，也可以在Model中定义数据修改和操作的业务逻辑；View 代表UI 组件，它负责将数据模型转化成UI 展现出来，ViewModel 是一个同步View 和 Model的对象。在…
ピエタ～幸せの青い鳥～相关
先打全所有升级补丁 不然没有end4 补丁下载页 4个end出现方法 只看律视角 选项任意→end1 只看愛视角 选项任意→end2 检查一下 这两个流程的CG是否收全了 开启唯视角以后有些CG是找不回的 只看唯视角 选项任意→end3 只看唯视角 最后一个选项选“唯” 此后只要律或愛的视角开…
【C++】C++11 STL算法(四)：二分查找法（Binary search operations）、合并操作
目录一、lower_bound1、原型：2、说明：3、官方demo二、upper_bound1、原型：2、说明：3、官方demo三、binary_search1、原型：2、说明：3、官方demo四、equal_range1、原型：2、说明：3、官…