首页 > 试题广场 >

数据流中的中位数

[编程题]数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

数据范围：数据流中数个数满足 $1 \le n \le 1000 \$ ，大小满足 $1 \le val \le 1000 \$

进阶：空间复杂度 $O(n) \$ ，时间复杂度 $O(nlogn) \$

示例1

输入

[5,2,3,4,1,6,7,0,8]

"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "

数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...

示例2

[1,1,1]

"1.00 1.00 1.00 "

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

堆排序

难度：

0条回答 2295收藏 109096浏览

查看代码

扫一扫，把题目装进口袋