保持不断扩大的阵列的平均轨道 [英] Keeping track of the median of an expanding array

问题描述

面试问题：

编辑在 您将得到一个数组。你让2堆出来的，一是minheap另一个最大堆。现在发现在O（n日志n）的时间。

Edited Below You are given an array. You make 2 heaps out of it, one minheap and the other max heap. Now find the median of the array using these 2 provided heaps in O(nlog n) time.

修正问题 数字是随机生成的，并存储成（膨胀）阵列。你将如何跟踪位数？

Corrected Question Numbers are randomly generated and stored into an (expanding) array. How would you keep track of the median?

解决方案 这个问题可以通过使用2堆来解决并且平均总能在O访问（1）的时间。

Solution This problem can be solved using 2 heaps and the median can always be accessed in O(1) time.

推荐答案

下面是你如何使用这两种堆。请注意，我假设你不知道元素的数量，这就是为什么我们必须跳出，直到我们流行的东西从最小堆是大于或等于我们从最大堆弹出。请注意，我们返回的平均，因为在一组的情况下，如 {1，2，3，4} 中位数实际上是 2.5 （两个中间值的平均值）。我假设双的值类型，但是这可以明显是任何东西。这里：

Here's how you use both heaps. Note that I'm assuming you don't know the number of elements, and this is why we must pop until we pop something from the min heap that is larger than or equal to what we pop from the max heap. Note that we return the average because in the case of a set like {1, 2, 3, 4} the median is actually 2.5 (the average of the two "middle" values). I'm assuming double as the value type, but this can obviously be anything. Here:

double min = minheap.pop();
double max = maxheap.pop();
while(min < max) {
    min = minheap.pop();
    max = maxheap.pop();
}

return (min + max) / 2;

由于大跌眼镜的是 O（log n）的，我们必须跳出为O（n / 2）值，这是为O（n log n）的。

Since popping is O(log n) and we have to pop O(n / 2) values, this is O(n log n).

这篇关于保持不断扩大的阵列的平均轨道的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！