O (n) алгоритм для нахождения медианы набора чисел

Question

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

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

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

Answer 1

Есть несколько возможностей. Мне нравится алгоритм Хоара Select. Основная идея аналогична быстрой сортировке, за исключением того, что когда вы выполняете рекурсию, вы выполняете рекурсию только в тот раздел, который будет содержать искомые числа.

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

Answer 2

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

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

1. Если мы упорядочили элементы C, число элементов слева от m-го старшего числа равно m ^ 2 (сумма нечетных чисел)

2. Числа, которые нас интересуют (для расчета медианы) а. Если n нечетно, то это (n ^ 2 + 1) / 2 = альфа б. Если n четное, тогда alpha1 = n ^ 2/2 и alpha2 = n ^ 2/2 + 1 но alpha1 = n ^ 2/2 никогда не бывает квадратным числом => число, расположенное непосредственно справа от alpha1, равно alpha1 (сумма первых m нечетных чисел является квадратной) => alpha1 = alpha2.

3. Таким образом, все сводится к определению m так, что m ^ 2 (сумма первых m нечетных чисел) чуть выше (n ^ 2/2)

4. Таким образом, все сводится к определению m = предельного значения (n / sqrt (2) и mth наибольшее число в исходной последовательности. *

5. Мы можем легко найти mth наибольшее число (просто продолжая отмечать первое m наибольшее число слева) или использовать медиану среднего медианного алгоритма, чтобы сделать это за линейное время.

Answer 3

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