Как найти медиану чисел за линейное время, используя кучи?

Ответ 2 · рейтинг 4 · Dale Hagglund

См. эту страницу в Википедии, посвященную алгоритмам выбора. В частности, посмотрите на алгоритм BFPRT и алгоритм Median of Medians. BFPRT является вероятностно-линейным и основан на быстрой сортировке; Медиана медиан гарантированно является линейной, но имеет большой постоянный коэффициент, поэтому на практике может потребоваться больше времени, в зависимости от размера вашего набора данных.

Если у вас есть всего несколько сотен или тысяч элементов, из которых нужно выбрать медиану, я подозреваю, что проще всего выполнить простую быструю сортировку с последующим прямым индексированием.

Ответ 3 · рейтинг 4 · fbrereto

Вероятно, есть лучшие алгоритмы, но вот как я это сделаю:

Имейте два ведра и значение. Значение является медианным, два сегмента "больше медианы" и "меньше медианы". Для каждого элемента x в массиве перебалансируйте сегменты так, чтобы big_bucket и small_bucket отличались по размеру не более чем на 1. При перемещении элементов из большого ведра в маленькое они сначала должны пройти через медианное значение, чтобы попасть туда (то есть разница в 2 успешно переместит элемент из одного ведра в другое, а разница в 1 переместит элемент от одного сегмента до медианного значения.) В конце вашего первого прохода по массиву значение должно быть вашим медианным значением.

Ответ 4 · рейтинг 3 · Shlomi

Возможно, его не было, когда был задан первоначальный вопрос, но теперь в вики есть ссылка на источник, и вот она: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf

В частности, перейдите на страницу 17 и посмотрите описание RSEL4. В теореме 3.2 они доказывают, что временная сложность этого k-го алгоритма выбора равна O(k). Таким образом, вам потребуется O (n), чтобы построить кучу, и дополнительно O (k), чтобы найти k-й наименьший элемент.

Это не так просто, как предполагалось в некоторых других ответах.

Ответ 5 · DarthVader

если вы знаете больше о структуре данных кучи, вы легко поймете, что это действительно так. Структура кучи может быть построена за время O (n), есть минимальная куча и максимальная куча. min корневой элемент кучи даст вам наименьший элемент. максимальный корневой элемент кучи даст вам максимальный элемент. Просто построив кучу, вы найдете мин и макс. та же идея для медианы и k-го наибольшего, при создании кучи вы можете найти медиану и k-й наибольший, посмотрев на левую или правую ветвь дерева и сохранив постоянный объем памяти для хранения номера элемента. и Т. Д.

Ответ 6 · jaycee

Сохраните первое целое число в массиве и установите счетчик равным 1. Затем выполните цикл по оставшимся целым числам в векторе. Если текущее целое число в массиве совпадает с сохраненным, счетчик увеличивается на единицу, в противном случае счетчик уменьшается на единицу. Если счетчик когда-либо достигнет нуля, выбросьте сохраненное целое число и замените его текущим целым числом в массиве. Когда вы, наконец, перебрали все целые числа, у вас остался один кандидат. Затем вам нужно снова пройтись по массиву и подсчитать появление кандидата, чтобы убедиться, что это действительно доминатор.

static int FindDominator(int[] arr)
{
int counter = 1;
int candidate = arr[0];
for(int i = 1; i < n; i++)
{
   if(arr[i] == candidate) counter++
    else
   {
        counter--;
        if(counter == 0) { candidate = arr[i]; counter = 1; }
    }
}
counter = 0;
for(int i = 0;  i < n; i++)
{
    if(arr[i] == candidate) counter++;
}
if(counter > n / 2) return candidate;
else return -1;
}

Ответ 7 · рейтинг -1 · Alan

Очевидно, что min и max в O(n) просты и не требуют кучи.

K-й самый большой можно сделать достаточно просто, поддерживая кучу k-размера верхних значений k на данный момент. Время выполнения будет O (n * logk). Вы могли бы назвать это линейным временем, если k имеет фиксированный размер и k ‹‹ n.

Я не думаю, что медиана возможна. Простое создание кучи размером O(n) требует времени O(n*logn).

Редактировать: Хорошо, если подумать, IVlad оказался прав. Вы можете создать кучу за O(n) фиксированного размера. Но ... это не помогает ОП с его медианным вопросом. Техника создания линейной кучи создает только допустимую кучу в качестве конечного результата. Простой подход к выполнению n вставок, приводящий к правильной куче после каждого шага, равен O(n*logn).

Мне кажется, что использование кучи для поиска медианы потребует использования этих работающих подкуч. Например, здесь был опубликован ответ (который, кажется, теперь удален), который ссылался на сообщение в блоге, предлагающее алгоритм для этой проблемы. Он отслеживал текущую медиану, используя две кучи (меньшую половину и большую половину), поскольку он выполняет один проход по данным. Это потребует более медленного, наивного подхода к куче, потому что он зависит от поддержания допустимых куч при вставке и удалении из них.

Есть ли другой способ найти медиану, используя линейную технику создания однократной кучи?