[剑指offer] 数据流中的中位数
本文首发于我的个人博客:尾尾部落
题目描述
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。
解题思路
我们可以将数据排序后分为两部分,左边部分的数据总是比右边的数据小。那么,我们就可以用最大堆和最小堆来装载这些数据:
- 最大堆装左边的数据,取出堆顶(最大的数)的时间复杂度是O(1)
- 最小堆装右边的数据,同样,取出堆顶(最小的数)的时间复杂度是O(1)
从数据流中拿到一个数后,先按顺序插入堆中:如果左边的最大堆是否为空或者该数小于等于最大堆顶的数,则把它插入最大堆,否则插入最小堆。然后,我们要保证左边的最大堆的size等于右边的最小堆的size或者最大堆的size比最小堆的size大1。
要获取中位数的话,直接判断最大堆和最小堆的size,如果相等,则分别取出两个堆的堆顶除以2得到中位数,不然,就是最大堆的size要比最小堆的size大,这时直接取出最大堆的堆顶就是我们要的中位数。
参考代码
import java.util.PriorityQueue; import java.util.Comparator; public class Solution { // 最小堆(右) private PriorityQueue<Integer> rHeap = new PriorityQueue<>(); // 最大堆(左) private PriorityQueue<Integer> lHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() { public int compare(Integer o1, Integer o2) { return o2 - o1; } }); // 保证lHeap.size()>=rHeap.size() public void Insert(Integer num) { // 先按大小插入,再调整 if(lHeap.isEmpty() || num <= lHeap.peek()) lHeap.offer(num); else rHeap.offer(num); if(lHeap.size() < rHeap.size()){ lHeap.offer(rHeap.peek()); rHeap.poll(); }else if(lHeap.size() - rHeap.size() == 2){ rHeap.offer(lHeap.peek()); lHeap.poll(); } } public Double GetMedian() { if(lHeap.size() > rHeap.size()) return new Double(lHeap.peek()); else return new Double(lHeap.peek() + rHeap.peek())/2; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
成为一名Java高级架构师到底需要学习什么?
Java架构师,应该算是一些Java程序员们的一个职业目标了吧。很多码农码了五六年的代码也没能成为架构师。那成为Java架构师要掌握哪些技术呢,总体来说呢,有两方面,一个是基础技术,另一个就是组织能力和提出解决方案能力了。我就跟大家来简要地说说吧。 如果你是想成为Java架构师,那么你首先要是一个Java高级攻城狮。也就是说,基础必须牢固,对Java的了解全面而且深入。 熟练使用各种框架,并知道它们实现的原理。 Jvm虚拟机原理、调优操作,懂得jvm能让你写出性能更好的代码; 池技术也是要掌握的,对象池、连接池、线程池都要会; Java反射技术,写框架必备的技术; Java各种集合对象的实现原理,了解这些可以让你在解决问题时选择合适的数据结构,高效地解决问题,写出代码; nio,注意“直接内存”的特点,使用场景。 还没完,除了上边那些,你还要熟练使用各种数据结构和算法,数组、哈希、链表、排序树等等都是;熟练使用Linux操作系统,也是必备的;熟悉各种协议,比如tcp协议,创建连接三次握手和断开连接四次握手的整个过程,不了解就没法对高并发网络应用做优化,http协议,session和co...
- 下一篇
Python3的LEGB规则
阐述LEGB前,需要先对Python的命名空间、作用域有一定的了解。 命名空间 命名空间表示变量的可见范围,一个变量名可以定义在多个不同的命名空间,相互之间并不冲突,但同一个命名空间中不能有两个相同的变量名。比如:两个叫“张三”的学生可以同时存在于班级A和班级B中,如果两个张三都是一个班级,那么带来的麻烦复杂很多了,在Python中你不能这么干。 在Python中用字典来表示一个命名空间,命名空间中保存了变量(名字)和对象的映射关系,在Python中命名空间出现在哪些地方呢?有函数范围内的命名空间(local),有模块范围内的命名空间(global),有python内建的命名空间(built-in),还有类对象的所有属性组成的命名空间。 命名空间的生命周期 所有的命名空间都是有生命周期的,对于python内建的命名空间,python解析器启动时创建,一直保留直至直python解析器退出时才消亡。而对于函数的local命名空间是在函数每次被调用的时候创建,调用完成函数返回时消亡,而对于模块的global命名空间是在该模块被import的时候创建,解析器退出时消亡。 作用域 一个作用域是指...
相关文章
文章评论
共有0条评论来说两句吧...