问题是我们如何找到整数值接收流的中位数（例如，对于 12、14、252、243、15，中位数是 15）O(log N)其中 N 是值的数量。请注意，我们有一个整数值流，因此通过接收每个值，我们必须重新找到中位数。
例子：
| Input | median
1 | 12 | 12
2 | 14 | 13 = (12+14)/2
3 | 252 | 14
.
.
.
P.S：使用此算法的一个例子是过滤图像。
好吧，随着问题的更新，意图很明确（不仅仅是找到中位数，而是每次收到新数字时重新找到中位数），我认为有办法。
我将从一对堆开始：最大堆和最小堆。最小堆将包含大于中位数的数字，最大堆将包含小于中位数的数字。当您收到第一个数字时，这就是您的中位数。当您收到第二个时，将两者中较小的插入到最大堆中，将两者中较大的插入到最小堆中。中位数是最小堆上最小的值和最大堆上最大的值的平均值。
除了两个堆之外，您还需要存储单个整数，当您收到奇数个输入时，该整数将成为当前的中位数。您将相当简单地填充它：如果您收到当前已满的输入，则基本上对这两个项目（新数字和旧中位数）进行排序，并将较小的插入到较小项目的堆中，将较大的插入到堆中对于较大的物品。新的中位数将是这两个堆的基数的平均值（并且您将另一个存储位置标记为空）。
当您收到一个空的新数字时，您会将新数字与中位数进行比较。如果它位于作为堆基数的数字之间，则它是新的中位数，您就完成了。否则，从必须包含中位数的基数中提取数字（如果新数字较大，则数字较大，如果新数字较小，则较小）并将其放入中位数位置，然后将新数字插入来自的堆中。
至少如果内存可用，提取/插入到堆中的时间应该是 O(log N)。我相信所涉及的其他一切都应该是恒定的复杂性。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
