Найти медиану из потока целых чисел

Учитывая несортированную последовательность целых чисел, которая втекает в вашу программу как поток.

Целые числа слишком велики, чтобы вписаться в память.

Предположим, что существует функция:

int getNext() throws NoSuchElementException;

Возвращает следующее целое число из потока.

Напишите функцию для поиска медианы.

Решите проблему в O (n).

Любые идеи?

Подсказка дана (используйте кучу структуры данных..)

Ответы

Ответ 1

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

Основным результатом здесь является N = размер данных, P = количество проходов

Теорема 2). Алгоритм P-pass, который выбирает наивысший из N элементов K th требует (N (1/ P) (log N) (2- 2/<суб > Pсуб > )).

Кроме того, для очень небольших объемов хранения S, то есть для 2 <= S <= O ((log N) 2), существует класс алгоритмов выбора, которые используют не более O ((log N) 3/S).

Прочтите документ. Я не совсем уверен, что куча имеет к этому отношение

Ответ 2

Вам нужно сохранить две кучи на одну максимальную кучу (которая содержит наименьшие элементы N/2, видимые до сих пор) и одну кучу минут (которая содержит самые большие элементы N/2). Храните лишний элемент в стороне, если N нечетно.

Всякий раз, когда вы вызываете функцию getNext(),

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

max (max-heap) <= дополнительный элемент <= min (min-heap).

Если N становится четным, сделайте то же, что и выше, чтобы получить второй дополнительный элемент. Затем добавьте меньшую до максимальной кучи, а большую - в мини-кучу. Вставка должна быть O (log N)

Получить медиану: O (1)
Если N нечетно, медиана является дополнительным элементом.
Если N четно, медиана представляет собой среднее значение между вершинами двух кучек

Ответ 3

Предположим, что окно для медианной поддержки - K. Построить двоичное дерево поиска для числа K. ОК); Сделайте обход в порядке и найдите (K/2) -й элемент. O (K/2);

Общее время O (K).

Ответ 4

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