现在的位置: 首页 > 综合 > 正文

如何维护一个中位数

2014年01月20日 ⁄ 综合 ⁄ 共 183字 ⁄ 字号 评论关闭

设计一个数据结构,包括两个函数,插入数据和获得中位数。

利用大根堆和小根堆,其中大根堆维护较小的一半数据,小根堆维护较大的一半数据。

然后根据相应的情况,对两个堆做相应的堆化操作,以满足两个堆中元素数目一致。时间复杂度O(lgn)

extension:

设计一个堆栈,除了常见的堆栈操作,还有一个返回中位数的操作。

同样利用大根堆和小根堆,来维护中位数。时间复杂度O(lgn)

抱歉!评论已关闭.