Найти медиану N 8-битных чисел

Задан массив из N 8-битных чисел (значение 0-255)?

Как найти медиану?

Я попробовал основную сортировку и медиану алгоритмов медиан.

Есть ли лучший способ, учитывая значения чисел от 0 до 255?

Источник

1 ответ

Решение

Используйте что-то похожее на подсчет сортировки.

  • Создайте массив "count" размером 256, инициализированный всеми 0. counts[x] будет количество раз x появляется во входном массиве.
  • Выполните итерацию по входному массиву, увеличивая значение в позиции в массиве count, соответствующее каждому значению во входном массиве (так counts[input[i]]++).
  • Зацикливайтесь на массиве count, суммируя все значения, пока не получите половину общего количества значений. Индексом будет искомое число (некоторая дополнительная логика, необходимая для работы с четным числом значений).

Это работает в 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 = counts[i]
         break
return median

Существуют и другие способы достижения той же сложности времени и пространства (хотя и несколько более сложные, чем описанные выше, и требующие изменения входного массива):

Источник
Другие вопросы по тегам