O (n), чтобы найти медиану набора чисел

Проблема: вход является (не обязательно отсортированной) последовательностью S = k1, k2,..., kn из n произвольных чисел. Рассмотрим набор C чисел n² вида min {ki, kj}, для 1 <= i, j <= n. Представьте время O(n) и O(n) пространственный алгоритм, чтобы найти медиану C.

До сих пор я нашел, исследуя C для разных множеств S, что количество экземпляров наименьшего числа в S в C равно (2n-1), следующее наименьшее число: (2n-3) и так пока вы не получите только один экземпляр наибольшего числа.

Есть ли способ использовать эту информацию для поиска медианы C?

Ответ 1

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

Например, если вы хотите, чтобы медиана из 100 номеров, вы должны начать с разбиения массива, как в Quicksort. Вы получите два раздела: один из которых содержит элемент 50 ^th. Рекурсивно выполните свой выбор в этом разделе. Продолжайте, пока ваш раздел не будет содержать только один элемент, который будет медианным (и обратите внимание, что вы можете сделать то же самое для другого выбранного вами элемента).

Ответ 2

Да, хорошая головоломка. Мы можем найти медианное развитие на линиях, которые вы сказали.

В C мы имеем 1 появление max (k), 3 появления следующего наивысшего, 5 следующего наивысшего и т.д.

Если бы мы упорядочили элементы из C, число элементов слева от m-го наивысшего числа равно m ^ 2 (сумма нечетных чисел)
Цифры, которые нас интересуют (для расчета медианы) а. Если n нечетно, то (n ^ 2 + 1)/2 = alpha б. Если n четно, тогда α1 = n ^ 2/2 и alpha2 = n ^ 2/2 + 1 но alpha1 = n ^ 2/2 никогда не является квадратным числом = > число, сразу справа от alpha1, равно альфа1 (сумма первых m нечетных чисел является квадратной) = > alpha1 = alpha2.
Таким образом, это сводится к определению m такого, что m ^ 2 (сумма первых m нечетных чисел) просто выше (n ^ 2/2)
Таким образом, это сводится к определению m = потолка (n/sqrt (2) и mth наивысшего числа в исходной последовательности. (Найти mth самый высокий или (nm-1) th самый низкий - это оптимизация).
Мы можем легко найти mth наивысшее число (просто сохраните первое наибольшее число слева) или использовать медианную медиану algortithm для выполнения этого в линейном времени.

Ответ 3

В Википедии есть хорошая статья о алгоритмах выбора. Если вы используете С++, STL включает в себя алгоритм nth_element() с линейным временем в среднем.

Ответ 4

Вам также может понравиться читать соответствующую информацию в этой книге ( "Массив массивных наборов данных: потоки данных главы" ) - он доступен на сайте Стэнфорда бесплатно!

Добыча массивных наборов данных