Бегущая медиана, движущаяся медиана, непрерывная медиана или медиана из динамического потока целых чисел – все это названия одной и той же хорошо известной проблемы кодирования. Вам предоставляется динамический поток целых чисел, следующих одно за другим случайным образом и без сортировки, и вы должны найти медиану текущего полученного набора целых чисел.
1. Давайте сначала определим, что такое медиана
Медиана – это “среднее” значение отсортированного набора чисел. Чтобы найти медиану, вы должны сначала отсортировать свой набор целых чисел в неубывающем порядке. Затем, если есть:
- нечетное число целых чисел, средний элемент – медиана. Например, в упорядоченном наборе:
2, 5, 6, 8, 10медиана равна6. - четное число целых чисел, среднего элемента нет; медиана вычисляется как среднее значение двух средних элементов. Пример в упорядоченном наборе:
3, 4, 7, 8, 10, 15медиана равна(7 + 8)/.5.
2. Формализуйте оператор динамического потока
Нам нужно написать функцию, чтобы получить среднее число динамического потока. Давайте подумаем о динамической потоковой (бегущей/движущейся/непрерывной) медиане как массиве чисел, которые вы считываете одно за другим, и после каждого числа вы хотите вывести медиану всех чисел.
Как мы собираемся это сделать?
3. Структура данных Кучи
Одним из наиболее эффективных способов решения этой проблемы является структура данных кучи.
Куча – это специальная древовидная структура данных, в которой дерево представляет собой полное двоичное дерево. В общем случае существует два типа кучи: Максимальная куча и Минимальная куча.
В Мини-куче:
- Корневой узел имеет минимальное значение.
- Значение каждого узла равно или больше значения его родительского узла.
В Максимальной куче:
- Корневой узел имеет максимальное значение.
- Значение каждого узла равно или меньше значения его родительского узла.
На самом деле, подход к куче является идеальным решением для вашей проблемы, потому что он позволяет нам эффективно извлекать самый большой элемент (максимальное значение) или самый маленький элемент (минимальное значение):
Когда придет число, мы сначала сравним его с текущей медианой и поместим в соответствующую кучу. Если новое целочисленное значение меньше текущей медианы, мы помещаем его в максимальную кучу, иначе мы помещаем его в минимальную кучу.
4. Давайте обратимся к коду
В Java класс PriorityQueue представляет собой кучу. Согласно определению PriorityQueue в Java – это особый тип очереди, в котором все элементы упорядочены в соответствии с их естественным порядком или на основе пользовательского компаратора, поставляемого во время создания. Давайте разделим решение на 4 основных шага.
ШАГ 1. функция getmedian
Это займет массив целых чисел и вернет массив двойников, подобный этому:
ШАГ 2. Метод добавления номера
это займет некоторое количество, приоритетная очередь из более низких и более высоких, как это:
ШАГ 3. метод перебалансировки
Перебалансировка выполняется путем перемещения самого большого элемента из максимальной кучи в минимальную кучу или путем перемещения самого маленького элемента из минимальной кучи в максимальную кучу:
ШАГ 4. метод получения медианы
Этот метод будет рассматривать два размера кучи, если они разные, возьмите верхний элемент из большей кучи. Если они одинакового размера, нам нужно будет их усреднить:
Спасибо вам за чтение!
Репозиторий Github можно найти здесь .
Чтобы связаться со мной, пожалуйста, проверьте мой Github , сеть LinkedIn или Твиттер .
Оригинал: “https://dev.to/ivanadokic/dynamic-stream-of-integers-median-m3o”