Сгенерированные случайным образом числа передаются методу. Напишите программу расчета медианы, динамически отслеживающую новые поступающие значения
4К открытий4К показов
Одно из возможных решений — использовать две кучи разных приоритетов: максимальная куча (maxHeap) для значений выше среднего и минимальная куча (minHeap) для значений ниже среднего. Это позволит разделить элементы примерно поровну с двумя значениями — вершинами куч. Теперь найти среднее значение очень просто.
Что означает «примерно поровну»? «Примерно» означает, что при нечетном количестве чисел в одной из куч окажется лишнее число. Можно сформулировать:
В алгоритме с балансировкой мы гарантируем, что maxHeap будет всегда содержать дополнительный элемент.
Алгоритм работает следующим образом. Если новое значение меньше или равно среднему, оно помещается в maxHeap, в противном случае оно попадает в minHeap. Размеры куч могут совпадать или в maxHeap может быть один дополнительный элемент. Это требование легко выполнить, сдвигая элемент из одной кучи в другую. Среднее значение находится в вершине. Обновления занимают O(log(n)) времени.
Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»
4К открытий4К показов