c++ - 在动态范围内找到中位数的最快方法

谁能建议任何方法或链接到c++中动态范围的快速中值查找的实现？例如，假设对于我的程序中的迭代，范围不断扩大，并且我想在每次运行中找到中值。

Range
4
3,4
8,3,4
2,8,3,4
7,2,8,3,4

因此，以上代码最终将为每行生成5个中值。

最佳答案

在不跟踪数组的排序副本的情况下获得的最佳结果是重新使用旧的中值，并通过线性时间搜索下一个最大的值来更新此值。这听起来很简单，但是，我们必须解决一个问题。

考虑以下列表(为了便于理解而排序，但您可以将它们按任意顺序排列):

    1, 2, 3, 3, 3, 4, 5
//           *

因此，这里的中位数是3(自列表排序以来的中间元素)。现在，如果您添加一个大于中位数的数字，则可能会将中位数向右“移动”一半索引。我看到两个问题:如何将指标提高一半？ (根据定义，中位数是接下来两个值的平均值。)当我们仅知道中位数是3时，我们如何知道中位数在哪个3上？

这不仅可以通过存储当前中位数，而且可以存储中位数在相同值内的位置来解决，这里它的“索引偏移量”为1，因为它是第二个3。在列表中添加一个大于或等于3的数字，会将索引偏移量更改为1.5。添加少于3的数字会将其更改为0.5。

当该数字小于零时，中位数发生变化。如果它超出了相等数(减去1)的数量(在本例中为2)，则还必须更改，这意味着新的中位数大于最后一个相等的数值。在这两种情况下，您都必须搜索下一个较小/下一个较大的数字并更新中间值。要始终知道索引偏移量的上限是多少(在本例中为2)，还必须跟踪相等数目的计数。

这应该使您大致了解如何在线性时间内实现中值更新。

关于c++ - 在动态范围内找到中位数的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15642813/