可能重复:
C中的滚动中值算法
鉴于从数据流中读取整数.到目前为止,以有效的方式查找元素的中位数.
解决方案我已经读过:我们可以使用左侧的最大堆来表示小于有效中位数的元素,在右侧使用最小堆来表示大于有效中位数的元素.
在处理传入元素之后,堆中元素的数量最多相差1个元素.当两个堆包含相同数量的元素时,我们发现堆的根数据的平均值为有效中值.当堆不平衡时,我们从包含更多元素的堆的根中选择有效中值.
但是我们如何构建最大堆和最小堆,即我们如何知道这里的有效中位数呢？我认为我们会在max-heap中插入1个元素,然后在min-heap中插入下一个元素,依此类推所有元素.纠正我如果我错在这里.
这是一个面试问题.设计一个类,它存储整数并提供两个操作:
void insert(int k) int getMedian()
我想我可以使用BST,因此insert需要O(logN)并getMedian取O(logN)(因为getMedian我应该为每个节点添加左/右子节点的数量).
现在我想知道这是否是最有效的解决方案,没有更好的解决方案.