算法：数据流中的中位数

ゝ一纸荒年。 2024-04-01 08:52 64阅读 0赞

![8ba8e4dbb987afbfd26d1c15afe66048.jpeg][]

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

例如，

*  \[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；
     *  为奇数时，中位数取小顶堆的堆顶元素。

**代码如下：**

![590a7781722d61d1693a14df44612c9d.jpeg][]

## 复杂度分析 ##

*  时间复杂度：
    
     *  addNum: O(logn)，其中 n 为累计添加的数的数量。
     *  findMedian: O(1)。
 *  空间复杂度：O(n)，主要为优先队列的开销。

## END ##

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

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

![63b823f2d4fa4caca9d8b4a344b1e3d2.png][]

[8ba8e4dbb987afbfd26d1c15afe66048.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3f4108b780264286b7eb134d2b5a4a09.jpeg
[590a7781722d61d1693a14df44612c9d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/454f3e253b8b4739a3726af511c9d0b7.jpeg
[63b823f2d4fa4caca9d8b4a344b1e3d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/24f18d3614de49a09b7d4120368dd1ae.png

发表评论取消回复

表情：

评论列表（有 0 条评论，64人围观）

还没有评论，来说两句吧...

相关阅读

相关算法：数据流中的中位数

![8ba8e4dbb987afbfd26d1c15afe66048.jpeg][] 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之

ゝ一纸荒年。/ 2024年04月01日 08:52/ 0 赞/ 65 阅读

相关 BM48 数据流中的中位数

描述如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之

àì夳堔傛蜴生んèń/ 2023年10月04日 17:47/ 0 赞/ 39 阅读

相关数据流中位数

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

╰+哭是因爲堅強的太久メ/ 2023年02月22日 08:26/ 0 赞/ 21 阅读

相关 47：数据流中的中位数

数据流中的中位数 public class Offer47 { //默认最小堆实现 PriorityQueue<Int

ゝ一世哀愁。/ 2022年11月26日 07:38/ 0 赞/ 130 阅读

相关数据流中的中位数

在牛客网上刷题时遇到这道题有新解法，特此来总结下~ ![这里写图片描述][SouthEast] 我开始是这么做的： import java.util.;

古城微笑少年丶/ 2022年06月12日 14:56/ 0 赞/ 193 阅读

相关剑指offer 数据流中的中位数

1.题目如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排

今天药忘吃喽~/ 2022年06月08日 05:53/ 0 赞/ 177 阅读

相关数据流中的中位数

写在前面 > 剑指offer：数据流中的中位数题目要求 > 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的

曾经终败给现在/ 2022年05月16日 12:22/ 0 赞/ 199 阅读

相关【题41】数据流中的中位数

【题目】如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序

爱被打了一巴掌/ 2022年03月01日 05:10/ 0 赞/ 213 阅读

相关数据流中的中位数

一、题目描述中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如， \[2,3,4\] 的中位数是 3 \[2,3\] 的中位数是

向右看齐/ 2021年11月04日 09:44/ 0 赞/ 368 阅读

相关剑指offer：数据流中的中位数

试题：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之

末蓝、/ 2021年06月24日 16:10/ 0 赞/ 380 阅读