Найти медиану несортированного массива без сортировки

Question

есть способ найти медиану несортированного массива: 1-, не сортируя его. 2- без использования алгоритма выбора или медианы медианов

Я нашел много других вопросов, подобных моим. Но решения, большинство из которых, если не все из них, обсуждали SelectProblem и MedianOfMedians

Answer 1

Вы, безусловно, можете найти медиану массива без сортировки. Нелегко это делать эффективно.

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

Или вы можете использовать кучу минут, размер которой равен половине размера массива. Создайте кучу, используя первую половину элементов массива, а затем для каждого оставшегося элемента x, если x больше минимума кучи, замените минимальный элемент на x. В конце, минимальный элемент кучи является медианным. Это время O (n log n) и O (n).

Answer 2

Неразрушающий режим selip() описан в http://www.aip.de/groups/soe/local/numres/bookfpdf/f8-5.pdf. Он делает несколько проходов через данные, на каждом этапе произвольно выбирает элементы в текущем диапазоне значений и затем подсчитывает количество элементов для определения рангов случайного выбора.

Answer 3

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

Я остану основную идею здесь. Для более подробного описания и доказательства того, почему работает этот алгоритм, отметьте .

Позвольте A быть вашим массивом и пусть n=|A|. Предположим, что все элементы A различны. Алгоритм выглядит следующим образом:

1. Случайно выберите t = n^(3/4) элементов из A.
2. Позвольте T быть «множеством» выбранных элементов. Сорт T.
3. Комплект pl = T[t/2-sqrt(n)] и pr = T[t/2+sqrt(n)].
4. Итерация по элементам A и определить, сколько элементов меньше, чем pl (обозначается l) и сколько больше, чем pr (обозначается r). Если l > n/2 или r > n/2, вернитесь к шагу 1.
5. Пусть M множество элементов в A между pl и pr. M можно определить на шаге 4, на всякий случай мы достигнем шага 5. Если размер M составляет не более 4t, сортируйте M. В противном случае вернитесь к шагу 1.
6. Возврат m = M[n/2-l] в качестве медианного элемента.

Основная идея алгоритма состоит в получении двух элементов (pl и pr), которые окружают срединный элемент (т.е. pl < m < pr), так что эти два очень близко один два друг с другом в упорядоченной версии (и делать это без фактической сортировки массива). С большой вероятностью все шесть шагов нужно выполнить только один раз (т. Е. Вы получите pl и pr с этими «хорошими» свойствами с первого и только прохождения через шаг 1-5, так что не возвращаясь к шагу 1). Когда вы найдете два таких элемента, вы можете просто отсортировать элементы между ними и найти медианный элемент A.

Шаг 2 и Шаг 5 действительно связаны с некоторой сортировкой (что может быть против «правил», которые вы загадочно установили: p). Если сортировка подматрица находится в таблице, вы должны использовать некоторый метод сортировки, который делает это в шагах O(slogs), где s - размер массива, который вы сортируете. Поскольку T и M значительно меньше A, этапы сортировки занимают «меньше» O(n) шагов. Если это также противоречит правилам сортировки подматрицы, тогда учтите, что в обоих случаях сортировка на самом деле не нужна. Вам нужно всего лишь найти способ определить pl, pr и m, что является еще одной проблемой выбора (с соответствующими индексами). При сортировке T и M это выполнится, вы можете использовать любой другой метод выбора (возможно, что-то rici, предложенное ранее).