发现平均在O（log n）的 [英] find median in O(log n)

问题描述

现在的问题是，我们怎样才能找到整数值的接收流的中位数（如12，14，252，243，15中位数为15）的 O（日志N）其中N是值的数量。请注意，我们有整数值流，因此通过接收每一个值，我们必须重新寻找中值。

The question is how we can find the median of a receiving stream of integer values(e.g. for 12, 14, 252, 243, 15 the median is 15) in O(log N) where N is number of values. Please note that we have a stream of integer values, hence by receiving each value, we have to re-find the median.

例如：

  | Input | median
1 |   12  |   12
2 |   14  |   13 = (12+14)/2
3 |   252 |   14
.
.
.

PS：使用该算法可以是滤波的图像的一个例子

P.S: An example of using this algorithm could be filtering an image.

推荐答案

好了，用更新的问题如此的意图是明确的（不只是找到位数，但每次你收到一个新的号码时重新找到位数），我认为有一种方式。

Okay, with the update to the question so the intent is clear (not just find the median, but re-find the median each time you receive a new number), I think there's a way.

我会从一对堆：一个最大堆和最小堆。最小堆将包含比中值大的号码，且最大堆比中值较小的数字。当您收到的第一个数字，这是你的中位数。当您收到第二个，你插入两个小到最大堆，两个较大的进分堆。中位数是那么最小的分堆，而最大的最大堆的平均值。

I'd start with a pair of heaps: a max-heap and a min-heap. The min-heap will contain the numbers larger than the median, and the max-heap the numbers smaller than the median. When you receive the first number, that's your median. When you receive the second, you insert the smaller of the two into the max-heap, and the larger of the two into the min-heap. The median is then the average of the smallest on the min-heap, and the largest on the max-heap.

随着两个堆，你需要存储一个整数，这将是目前的中位数，当您收到输入奇数。你会填充的相当简单：如果你收到一个输入，它现在还是空的，你基本上这两个项目进行排序，然后插入小到堆较小的物品，和更大的进堆较大的项目。然后，您的新的中位数将是这两个堆的基础的平均值（你会标记其他存储位置为空）。

Along with the two heaps, you'll want storage for a single integer that will be the current median when you've received an odd number of inputs. You'll populate that fairly simply: if you receive an input with it currently empty, you basically sort those two items and insert the smaller into the heap for the smaller items, and larger into the heap for larger items. Your new median will then be the mean of the bases of those two heaps (and you'll mark the other storage location as empty).

当您收到一个新的号码与空，你会比较新的号码位数。如果它的数字作为堆的基极之间，它是新的中位数，就大功告成了。否则，提取的基础，必须持有的中位数（较大的新号码的数字越大，小的，如果它的体积更小），并把它放入中间点的数量，然后插入新的号码到堆，堆是从哪里来的。

When you receive a new number with that empty, you'll compare the new number to the median. If it's between the numbers as the bases of the heaps, it's the new median, and you're done. Otherwise, extract the number from the base that must hold the median (larger numbers of the new number is larger, smaller if it's smaller) and put it into the median spot, then insert the new number into heap that came from.

至少如果没有记错，提取/插入堆应为O（log N）。我相信一切参与应该是恒定的复杂性。

At least if memory serves, the extract/insert into a heap should be O(log N). I believe everything else involved should be constant complexity.

这篇关于发现平均在O（log n）的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！