algorithm - 求 N 个 8 位数字的中位数

Question

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

如何找到中位数？

我尝试了基数排序和中位数算法的中位数。

鉴于数字的值在 0 到 255 之间，有没有更好的方法？

Answer 1

使用类似于计数排序的东西。

• 创建一个大小为 256 的“计数”数组，初始化为全 0。counts[x]将是x出现在输入数组中的次数。
• 迭代您的输入数组，递增 counts 数组中与输入数组中的每个值相对应的位置中的值 (so counts[input[i]]++)。
• 循环计数数组，将所有值相加，直到得到值总数的一半。索引将是我们正在寻找的数字（处理偶数个值需要一些额外的逻辑）。

这使用空间在O(n)时间上运行O(1)（这是渐近最优的）。

就像这样：（伪代码）

// 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

---

还有其他方法可以实现相同的时间和空间复杂度（尽管比上面的复杂一点，并且需要您修改输入数组）：

• 快速排序的一种变体，通过在每一步将数组分成 3 个而不是 2 个（更小、相等和更大的值）来优化重复值。

• 就地基数排序的一种变体。

• 中位数算法的中位数实际上也具有这种复杂性。