这是一道面试题。您需要设计一个包含整数值的队列，并具有一个 getMedian() 函数，该函数返回当前队列的中值元素。您可以使用 O(n) 额外空间。
getMedian() 可以用时间复杂度 < O(n) 来实现吗？
例如：当队列具有以下值（2、1、2、2、6、4、2、5）时，此方法返回 2 并且不会删除该对象。
问问题
1084 次
1 回答
9
您的问题的已知实现如下：
您需要实现的是 2 个堆，一个是最小堆，另一个是最大堆。
您还需要一个整数来告诉我们队列中的对象数量。
堆的约束如下：
1. min-heap 将具有队列中较大的对象
2. max-heap 将具有队列中较小的对象
3. max-heap 将具有相同或多 1 个对象对象比你的最小堆
这样，如果您有奇数个对象，则中位数将恰好是您的最大堆中的最大对象。如果您有偶数个对象，那么您的中位数将是堆的两个根的平均值（最大堆的最大值，最小堆的最小值）。
重要的是要注意，如果您的堆变得不均匀，例如，如果您要从某个堆中“弹出”，您将需要从另一个堆中移除并移动它。但这不是问题，因为您需要处理的只是堆的根，仅此而已。
getMedian 的时间复杂度变为 O(1)
刚刚找到一篇关于这个主题的文章：链接
回复评论
最大堆包含一半最小的元素。
当您向队列中添加新号码时，您首先检查队列中的对象数量。
如果要添加的数字是偶数，则意味着需要将其添加到最大堆中，因为两个队列的大小相等。
然后您会看到最大堆中的最大值是多少。
如果它大于你的数字，你可以将它插入到最大堆中。
如果它更小，则意味着您的新数字可能大于最小堆中的数字。
所以你会看到 min-heap 中的 min 是什么。
如果您的数字小于最小值，则可以将其插入最大堆中，如果更大，则将最小堆中的最小值移动到最大堆中，然后将新数字插入到最小堆中堆。
如果数字是奇数，则需要添加到最小堆中，因为最大堆还有一个，依此类推..
它有点复杂，但如果你仍然不明白，我不介意为你编写伪代码
于 2012-09-18T15:01:02.033 回答