找出 N 个 8 位数字的中位数

Question

给定一个包含 N 个 8 位数字（值 0-255）的数组？

如何求中位数？

我试过基数排序和中位数算法。

鉴于数字的值介于 0 和 255 之间，是否有更好的方法？

Answer 1

使用类似于 counting sort 的内容。

创建一个 "counts" 大小为 256 的数组，初始化为全 0。 counts[x] 将是 x 在输入数组中出现的次数。
遍历您的输入数组，递增计数数组中与输入数组中每个值对应的位置的值（因此 counts[input[i]]++）。
遍历计数数组，对所有值求和，直到达到值总数的一半。索引将是我们正在寻找的数字（处理偶数个值需要一些额外的逻辑）。

使用 O(1) space（渐近最优），这在 O(n) 时间内运行。

类似于：（伪代码）

// Count the number of occurrences of each value.
counts[256] = {0}
for i = 0 to input.length
   counts[input[i]]++

// Get the median.
count = input.length
sum = 0
if count divisible by 2
   first = NaN
   for i = 0 to counts.length
      sum += counts[i]
      if first == NaN && sum >= count / 2
         first = i
      if sum >= count / 2 + 1
         median = (first + i) / 2
         break
else
   for i = 0 to counts.length
      sum += counts[i]
      if sum >= (count + 1) / 2
         median = i
         break
return median

还有其他方法可以达到同样的时间和space的复杂度（虽然比上面的复杂一点，而且需要修改输入数组）：

A variant of quick sort 通过在每一步（更小、相等和更大的值）将数组拆分为 3 个而不是 2 个来针对重复值进行优化。
A variant of radix sort 就地。
The median of medians algorithm 实际上也有这种复杂性。

找出 N 个 8 位数字的中位数

Find median of N 8-bit numbers

sorting

algorithm

radix-sort

median

median-of-medians