跟踪中位数的最佳方法是什么？

Question

我读了一个问题，我正在寻找关于如何解决这个问题的意见：

数字是随机生成的，并存储在一个(扩展)数组中，您如何跟踪中位数？

有两种数据结构可以解决这一问题。一个是平衡二叉树，另一个是保持最大一半和最小一半元素轨迹的两个堆。我认为这两种解决方案的运行时间与O(n lg n)相同，但我不能肯定我的判断。

跟踪中位数的最佳方法是什么？

我的尝试：

在这个问题中，我认为堆是跟踪中位数的最好方法。有两个堆，大堆和小堆，它们不需要是顺序的。首先，我们计算数组中元素的平均值。如果元素小于平均值，则将num放入小堆中。相反，我们把数字放进了大堆里。如果大堆的数目等于小堆的数目，那么在小堆中最大的堆和大堆中最小的堆是中位数。如果这两个堆有不同的大小，我们只需从大小较大的堆中弹出根元素，并将其推送到较小大小堆的根。对于大堆，根元素是最小的，对于小堆，根元素是最大的。这样，如果两个堆具有相同的大小或数字差异，我们就会在根中找到介质。

我认为这个解有O(m*n)的运行时间，m表示我们调整不平衡堆的时间。

这是追踪中位数的最好方法吗？

Answer 1

可能有两个以上的数据结构解决了这个问题。看看在一次传递中使用内存有限的近似中介和其他分位数

他们不用两堆。我想您可以修改它们的算法，以周期性地得到中间值的近似值。当然，一个近似有多好，取决于许多因素，其中最重要的是有多少数据通过了算法。

Answer 2

更好的解决方案是使用跳过列表。由于要插入的列表始终保持为排序列表(根据构建过程的实际情况)，插入的复杂性为O(log )。您将利用以下事实:第一个插入将以零成本提供中位数(插入项为中位数)。在每次额外的插入之后，您的列表仍然是排序的，中位数本身将根据单个索引向上或向下移动，这种比较是O(1)。

总复杂度= O(log )