nc131专题

NC131 随时找到数据流的中位数

描述 有一个源源不断的吐出整数的数据流,假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构,MedianHolder可以随时取得之前吐出所有数的中位数。 [要求] 1. 如果MedianHolder已经保存了吐出的N个数,那么将一个新数加入到MedianHolder的过程,其时间复杂度是O(logN)。 2. 取得已经吐出的N个数整体的中位数的过程,时间复杂度为O(