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

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

我认为您可以使用最小-最大-中值堆。每次更新数组时，您只需要log(n)时间来找到新的中值。对于最小-最大-中位数堆，根是中间值，左边是最小-最大堆，而右侧是最大-最小堆。有关详细信息，请参阅论文“最小-最大堆和通用优先级队列”。

Answer 3

在下面的代码中，我修改了这个stack，给出了你所需要的输出

    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];
        }
    }