【解题报告】【lintcode81】Data Stream Median

题意

给出一组数字,逐一输入,每输入一个数字,就输出已经输入数字排序后的中位数,即中间那个数字

解答

直接暴力很简单,但是时间复杂度很高,不符合性能要求。
时间复杂度要求是nlogn,可以想到的是快速排序和堆排序两种排序,再结合题目,我们选择堆

维护两个堆,一个堆比中位数小,一个比中位数大,我们称之为大堆,小堆

大堆是一个比中位数大的小根堆,堆顶是刚刚比中位数大的数

小堆是一个比中位数小的大根堆,堆顶是刚刚比中位数小的数

每次获得一个数的时候,先与目前的中位数比较,大就加入大堆,小就加入小堆,如果加入完毕之后两个堆的大小不一致了,就应该重新查找中位数了
1.如果大根堆比小根堆大,先把中位数放入小堆,再从大堆拿出堆顶
2.如果小堆比大堆大,同上
由于对堆的维护时间复杂度是logn满足了我们的需求
这样,我们就能每次logn的复杂度拿到中位数了

代码

u3coding
A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.