本文主要是介绍NC131 随时找到数据流的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。
[要求]
1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。
2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)
每行有一个整数opt表示操作类型
若opt=1，则接下来有一个整数N表示将N加入到结构中。
若opt=2，则表示询问当前所有数的中位数
示例1
输入：
[[1,5],[2],[1,3],[2],[1,6],[2],[1,7],[2]]
复制返回值：
[5,4,5,5.5]
复制说明：
第一次查询时结构内的数为：5 第二次查询时结构内的数为：3 5 第二次查询时结构内的数为：3 5 6 第二次查询时结构内的数为：3 5 6 7
思路1
- 列表，排序；本题要求实现数据结构能够随时找出数据流的中位数，所以该数据结构需要依据数据的添加实时更新中位数；
- 中位数（Median）又称中值，统计学中的专有名词，是按顺序排列的一组数据中居于中间位置的数；对于奇数个取中间值，对于偶数个数据则取中间两个值的平均值；
- 故可以使用列表来存储数据，并且在每次添加数据时，对列表进行一次升序排序，并找出新列表的中位数，更新中位数的记录&#
这篇关于NC131 随时找到数据流的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
