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

Question

任何人都可以建议任何方法或链接到 C++ 中动态范围的快速中值查找的实现吗？例如，假设对于我的程序中的迭代，范围会增加，并且我想在每次运行时找到中位数。

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

所以上面的代码最终会为每一行产生 5 个中值。

Answer 1

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

考虑下面的列表（为了更容易理解而排序，但您将它们保持在任意顺序）：

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

所以在这里，中位数是3（列表排序后的中间元素）。现在，如果您添加一个大于中位数的数字，这可能会将中位数向右“移动”一半索引。我看到了两个问题：我们怎样才能将指数提高一半？（根据定义，中位数是接下来两个值的平均值。）3当我们只知道中位数是 时，我们如何知道中位数是3多少？

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

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

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

Answer 2

我认为您可以使用 min-max-median 堆。每次更新数组时，您只需要 log(n) 时间即可找到新的中值。对于最小-最大-中值堆，根是中值，左侧树是最小-最大堆，而右侧是最大-最小堆。有关详细信息，请参阅论文“Min-Max Heaps and Generailized Priority Queues”。

Answer 3

在下面找到一些代码，我已经重新设计了这个堆栈以提供您必要的输出

    private void button1_Click(object sender, EventArgs e)
    {
        string range = "7,2,8,3,4";
        decimal median = FindMedian(range);
        MessageBox.Show(median.ToString());

    }

    public decimal FindMedian(string source)
    {
        // Create a copy of the input, and sort the copy

        int[] temp = source.Split(',').Select(m=> Convert.ToInt32(m)).ToArray();
        Array.Sort(temp);

        int count = temp.Length;
        if (count == 0) {
            throw new InvalidOperationException("Empty collection");
        }
        else if (count % 2 == 0) {
            // count is even, average two middle elements
            int a = temp[count / 2 - 1];
            int b = temp[count / 2];
            return (a + b) / 2m;
        }
        else {
            // count is odd, return the middle element
            return temp[count / 2];
        }
    }