use*_*359 6 algorithm data-structures
这是一个面试问题.您需要设计一个包含整数值的队列,并且具有一个getMedian()函数,该函数返回当前队列的中值元素.您可以使用O(n)额外空间.
可以用时间复杂度<O(n)实现getMedian()吗？
例如:当队列具有以下值(2,1,2,2,6,4,2,5)时,此方法返回2并且不删除该对象.
您的问题的已知实现如下:
你需要实现的是2堆,一个是最小堆,另一个是最大堆.
您还需要一个整数来告诉我们队列中的对象数量.
堆的约束如下:
1.最小堆将具有队列
2 的较大对象.最大堆将具有队列
3 的较小对象.最大堆将具有相同或1个以上对象比你的最小堆
这样,如果你有一个奇数个对象,那么中位数就是你的最大堆中的最大对象.如果你有一个偶数个对象,你的中位数将是你的两个根的平均值(最大堆的最大值,最小堆的最小值).
重要的是要注意,如果您的堆变得不均匀,例如,如果您将从某个堆"弹出",则需要从其他堆中移除并移动它.但这不是问题,因为您需要处理的只是堆积物的根源而已.
getMedian的时间复杂度变为O(1)
刚刚找到一篇关于这个主题的文章:链接
回答评论
max-heap保存半个最小的元素.
向队列添加新编号时,首先要检查队列中的对象数.
如果要添加的数字是偶数,则表示需要将其添加到max-heap,因为两个队列的大小相等.
然后,您可以看到max-heap中的最大值.
如果它大于你的数字,你可以将它插入max-heap.
如果它更小,意味着你的新数字可能大于最小堆中的数字.
所以你看看min-heap中的min是多少.
如果你的数字小于min,那么你可以将它插入max-heap中,如果它更大,那么你将min-heap中的min移动到max-heap,然后在min-中插入你的新数字堆.
如果数字是奇数,则需要添加到最小堆,因为最大堆还有一个,依此类推.
它有点复杂,但如果你仍然不明白我不介意psuedo为你编码