algorithm - 如何在不存储列表的情况下计算或近似列表的中位数

Question

我正在尝试计算一组值的中位数，但我不想存储所有值，因为这可能会超出内存要求。有没有一种方法可以在不存储和排序所有单个值的情况下计算或近似中位数？

理想情况下，我想编写如下代码

var medianCalculator = new MedianCalculator();
foreach (var value in SourceData)
{
  medianCalculator.Add(value);
}
Console.WriteLine("The median is: {0}", medianCalculator.Median);

我只需要实际的 MedianCalculator 代码!

更新:有些人问我尝试计算中位数的值是否具有已知属性。答案是肯定的。一个值以 0.5 为增量，从大约 -25 到 -0.5。另一个也是从 -120 到 -60 以 0.5 为增量。我想这意味着我可以为每个值使用某种形式的直方图。

谢谢

尼克

Answer 1

如果值是离散的并且不同值的数量不是太多，您可以只累加每个值在直方图中出现的次数，然后从直方图计数中找到中位数(只需将直方图的顶部和底部，直到到达中间)。或者，如果它们是连续值，您可以将它们分配到箱子中——这不会告诉您确切的中位数，但它会给您一个范围，如果您需要更精确地了解，您可以再次遍历列表，只检查中央仓中的元素。