在无序列表的多个子范围中查找中位数

Question

例如,给定N个元素的无序列表,找到子范围0..100,25..200,400..1000,10..500的中位数......我没有看到比通过每个元素更好的方法子范围并运行标准中位数查找算法.

一个简单的例子:[5 3 6 2 4] 0..3的中位数是5.(不是4,因为我们询问原始列表的前三个元素的中位数)

Answer 1

我认为随着子范围数量的增加，您很快就会发现排序然后检索所需的元素编号会更快。

在实践中，因为您可以调用高度优化的排序例程。

从理论上讲，也许在实践中也是如此，因为由于您正在处理整数，因此您不需要为排序支付 n log n - 请参阅http://en.wikipedia.org/wiki/Integer_sorting。

如果您的数据实际上是浮点而不是 NaN，那么稍微调整一下实际上就可以让您对它们使用整数排序 - 来自 - http://en.wikipedia.org/wiki/IEEE_754-1985#Comparing_floating-point_numbers -二进制表示具有特殊属性，除了 NaN，任何两个数字都可以像符号和大小整数一样进行比较（尽管对于现代计算机处理器，这不再直接适用）：如果符号位不同，则负数在正数之前数（除了负零和正零应被视为相等），否则，相对顺序与字典顺序相同，但对于两个负数相反；字节顺序问题适用。

因此，您可以检查 NaN 和其他有趣的东西，假设浮点数是符号 + 大小整数，当负数时减去以纠正负数的顺序，然后将其视为正常的 2 补码有符号整数，排序，然后反转该过程。