欢迎光临散文网 会员登陆 & 注册

算法:数据流中的中位数

2022-10-20 11:23 作者:做架构师不做框架师  | 我要投稿



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


例如,

  • [2,3,4] 的中位数是 3

  • [2,3] 的中位数是 (2 + 3) / 2 = 2.5


设计一个支持以下两种操作的数据结构:

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。

  • double findMedian() - 返回目前所有元素的中位数。


示例1

  • 输入:

["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]

[[],[1],[2],[],[3],[]]

  • 输出:

[null,null,null,1.50000,null,2.00000]


限制

  • 最多会对 addNum、findMedian 进行 50000 次调用。


方法:优先队列

  • MedianFinder:

    • 我们创建两个优先队列,分别保存列表的一半:

    • 小顶堆,保存值较大的一半;

    • 大顶堆,保存值较小的一半;

  • addNum:

  • 为偶数时,向大顶堆中加入当前值,再将大顶堆的堆顶元素插入到小顶堆;

  • 为奇数时,向小顶堆中加入当前值,再将小顶堆的堆顶元素插入到大顶堆;

  • findMedian:

    • 为偶数时,中位数取两个堆顶元素之和除以2;

    • 为奇数时,中位数取小顶堆的堆顶元素。


代码如下:


复杂度分析

  • 时间复杂度:

    • addNum: O(logn),其中 n 为累计添加的数的数量。

    • findMedian: O(1)。

  • 空间复杂度:O(n),主要为优先队列的开销。


END

骐骥一跃,不能十步;驽马十驾,功在不舍;锲而舍之,朽木不折;锲而不舍,金石可镂,赠友人。

好兄弟可以点赞并关注我的公众号“javaAnswer”,全部都是干货。


算法:数据流中的中位数的评论 (共 条)

分享到微博请遵守国家法律