求N个8位数的中位数

Question

给定N个8位数字的数组(值0-255)？

如何找到中位数？

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

如果数字的值在0到255之间,有没有更好的方法？

Answer 1

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

• 创建一个大小为256的"count"数组,初始化为全0.counts[x]将是x输入数组中出现的次数.
• 迭代输入数组,递增计数数组中与输入数组中每个值对应的位置的值(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来优化重复值(更小,相等和更大的值).

• 基数排序的变体就地.

• 中位数算法的中位数实际上也分享了这种复杂性.