Учитывая несортированную последовательность целых чисел, которая втекает в вашу программу как поток.
Целые числа слишком велики, чтобы вписаться в память.
Предположим, что существует функция:
int getNext() throws NoSuchElementException;
Возвращает следующее целое число из потока.
Напишите функцию для поиска медианы.
Решите проблему в O (n).
Любые идеи?
Подсказка дана (используйте кучу структуры данных..)
Смотрите документ. Он (скорее всего) займет более одного прохода. Идея состоит в том, что в каждом проходе вычисляются верхняя и нижняя границы, так что между ними лежит медиана.
Основным результатом здесь является 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).
Прочтите документ. Я не совсем уверен, что куча имеет к этому отношение
Вам нужно сохранить две кучи на одну максимальную кучу (которая содержит наименьшие элементы N/2, видимые до сих пор) и одну кучу минут (которая содержит самые большие элементы N/2). Храните лишний элемент в стороне, если N нечетно.
Всякий раз, когда вы вызываете функцию getNext(),
Если N становится нечетным, сохраните новый элемент в качестве дополнительного элемента. При необходимости замените этот элемент на один из мини-кучи или макс-кучи, чтобы выполнить следующее условие
max (max-heap) <= дополнительный элемент <= min (min-heap).
Если N становится четным, сделайте то же, что и выше, чтобы получить второй дополнительный элемент. Затем добавьте меньшую до максимальной кучи, а большую - в мини-кучу. Вставка должна быть O (log N)
Получить медиану: O (1)
Если N нечетно, медиана является дополнительным элементом.
Если N четно, медиана представляет собой среднее значение между вершинами двух кучек
Предположим, что окно для медианной поддержки - K. Построить двоичное дерево поиска для числа K. ОК); Сделайте обход в порядке и найдите (K/2) -й элемент. O (K/2);
Общее время O (K).
Используя алгоритм выбора, мы можем достичь этого в сложности O (n). Но я до сих пор не понимаю, как использовать кучу в этом случае.