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

Question

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

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

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

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

Answer 1

Используйте что-то похожее на counting sort.

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

Это пробегает 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 

---

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

• A variant of quick sort, который оптимизирован для повторяющихся значений путем разделения массива на 3 вместо 2 на каждом шаге (меньше, равного и большие значения).

• A variant of radix sort который находится на месте.

• The median of medians algorithm также на самом деле разделяет эту сложность.