在O(log n)时间复杂度内查找中位数

Question

在O(log n)时间复杂度内查找中位数

8

问题是如何在接收整数值的流中找到中位数（例如，对于12、14、252、243、15，中位数是15），时间复杂度为O(log N)，其中N是值的数量。请注意，我们有一个整数值的流，因此通过接收每个值，我们必须重新查找中位数。

示例：

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

顺便提一下，使用该算法的一个示例是图像滤波。

- csuo

3

除非数据已排序且具有随机访问性，否则我相当确定你所能期望的最佳时间复杂度为线性。 - Jerry Coffin

嗨Jerry，你说得对，当我们有一个N个值的列表时，我们应该对列表进行排序（O（N log N）），但正如我所提到的，这里的问题有点不同，我们有一系列输入流。 - csuo

nlogn是最小的。 - Prajval M

3个回答

4

（我假设您正在寻找一种算法，该算法可以在对于一个包含n个现有数字和一个新数字的集合，以对数时间查找新集合中的中位数，从而使添加n个数字的总运行时间为O(n lg n)。）可能已经有一种名为此目的的算法了，但这是我的想法：维护一个红黑树，将数字按到达顺序插入其中。在每个节点上，除了存储数字本身和子/父指针外，还存储一个整数，该整数告诉位于此节点以下的节点数（为了方便起见，包括此节点本身）。我非常确定在每次插入操作时更新此信息可以在对数时间内完成，即使需要进行树旋转。借助嵌入在树中的这些信息，如果您还跟踪树中节点的数量，则可以在对数时间内定位中位数。（这可能是一个略微高级的描述；如果需要更多细节，请告诉我。）

- Aasmund Eldhuset

你说得完全正确，我正试图按照你所说的那样做，但问题在于仅通过标记每个节点的子节点数量来查找中位数有些困难。 - csuo

1

这在《算法导论（第二版）》的第14.3节“增强数据结构-区间树”中有详细分析。 - Karoly Horvath

@mahD：如果你有23个元素，第11个元素（从0开始计数）就是中位数。如果根节点的左子节点说它的子树包含9个元素，那么你知道中位数既不在左子树中，也不是根节点，所以它必须在右子树中，其中包含第10到第22个元素。因此，相对于该子树，现在要寻找第1个元素。递归执行此算法。 - Aasmund Eldhuset

再次感谢您的回答。另一个问题是，如果我们有相同的值（例如10 8 7 7 5），会发生什么？ - csuo

@mahD：处理重复数字最简单的方法可能是将它们作为新的唯一节点插入。任何二叉搜索树的标准规则是左子树中的所有元素必须小于或等于根元素，因此这是完全允许的。也可以在每个节点中拥有一个“numberOfOccurrences”字段，但这样搜索逻辑就会稍微复杂一些。 - Aasmund Eldhuset

2

霍尔选择算法（也称为快速选择）可以在平均时间 O(n) 内完成此操作。

它基本上是使用随机主元递归地将数据集分区，并检查适当的部分。还有一种中位数中位数算法，它保证了最坏情况下 O(n) 的时间复杂度，但通常情况下这种算法会导致过度处理。

- Karoly Horvath

1

我认为他正在寻找一种在线算法，该算法可以在输入每个新数字时生成新数字集合的中位数。这可以比使用median-select更快地完成。 - Aasmund Eldhuset

1

他在问题中没有提到这一点，如果是这样的话，那么区间树是完美的选择... 如果他只需要整个流的中位数，那么快速选择算法也可以。 - Karoly Horvath

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jerry Coffin · Accepted Answer

好的，对于问题的更新（不仅仅是找到中位数，而是每次收到一个新数字都要重新寻找中位数），我认为有一种方法。

我会从一对堆（最大堆和最小堆）开始。最小堆将包含大于中位数的数字，最大堆将包含小于中位数的数字。当您收到第一个数字时，那就是您的中位数。当您收到第二个数字时，将较小的放入最大堆，将较大的放入最小堆。中位数是最小堆上最小值和最大堆上最大值的平均值。

除了这两个堆之外，您还需要一个整数的存储空间，用于在输入奇数个数字时成为当前中位数。你可以简单地处理它：如果你收到一个已经填满它的输入，你基本上会对那两个项（新数字和旧中位数）进行排序，并将较小的插入较小项的堆中，较大的插入较大项的堆中。然后将新中位数设置为这两个堆的基础的平均值（并将另一个存储位置标记为空）。

当您收到一个空的中位数时，您将比较新数字和中位数。如果它在堆的基础数字之间，那么它就是新的中位数，你完成了。否则，请从必须容纳中位数的基础数字中提取数字（如果新数字更大，则为较大数字；如果新数字更小，则为较小数字），并将其放入中位数位置，然后将新数字插入该堆。

至少如果我的记忆没有出错，从堆中提取/插入应该是O(log N)的时间复杂度。我相信其他所有涉及到的操作都应该是常数复杂度。