Учитывая массив N 8-разрядных чисел (значение 0-255)?Найти медиану N-битовых чисел
Как найти медиану?
Я пробовал сортировку radix и медиану алгоритмов медианов.
Есть ли лучший способ, если значения чисел находятся между 0 и 255?
Учитывая массив N 8-разрядных чисел (значение 0-255)?Найти медиану N-битовых чисел
Как найти медиану?
Я пробовал сортировку radix и медиану алгоритмов медианов.
Есть ли лучший способ, если значения чисел находятся между 0 и 255?
Используйте что-то похожее на counting sort.
counts[x]
будет числом раз x
появляется во входном массиве.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 = counts[i]
break
return median
Есть другие способы достижения того же времени и пространства сложности (хотя и немного более сложным, чем выше, и требуя, чтобы изменить входной массив):
A variant of quick sort, который оптимизирован для повторяющихся значений путем разделения массива на 3 вместо 2 на каждом шаге (меньше, равного и большие значения).
A variant of radix sort который находится на месте.
The median of medians algorithm также на самом деле разделяет эту сложность.