Find Median from Data Stream

Сложная№295две кучи

Нужно написать класс: он получает числа по одному через addNum и по вызову findMedian возвращает медиану всех пришедших чисел — среднее из них при нечётном количестве и полусумму двух средних при чётном. Наш пример: addNum(5), addNum(8), findMedian(), addNum(2), addNum(1), findMedian(), addNum(9), findMedian() — медианы 6.5, 3.5 и 5.

295 Find Median from Data StreamРазбор · 1×

Пример: addNum получает 5, 8, 2, 1, 9, а findMedian() вызывается после 8, 1 и 9. Посередине low растёт влево, high — вправо; их верхи смотрят друг на друга.

addNum(x)58219low, макс-кучаhigh, мин-куча——findMedian—
ещё не добавленоx или переносимое числодобавлено; в кучеверх кучимедиана: прочитанные верхи, ответ

Создаём MedianFinder(): init выполняется один раз

01/38
сначала · назад · пуск · шаг
Скорость
1class MedianFinder:
2 function init():
3 low = empty max-heap // smaller half
4 high = empty min-heap // larger half
5 function addNum(x):
6 if low is empty or x <= max of low:
7 push x into low
8 else:
9 push x into high
10 if size of low > size of high + 1:
11 push (pop max from low) into high
12 else if size of high > size of low:
13 push (pop min from high) into low
14 function findMedian():
15 if size of low > size of high:
16 return max of low
17 return (max of low + min of high) / 2
состояние
x
–
low
–
high
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Число попадает в low, только если оно не больше верха low, а переносятся числа только с верхов. Поэтому всё в low не больше всего в high.
  2. После каждого addNum в low столько же чисел, сколько в high, или на одно больше. Значит, середина отсортированных чисел — прямо на верхах: верх low или среднее двух верхов.
  3. По 5 видно, зачем нужны оба переноса: 1 выводит low вперёд на два, и 5 уходит в high; 9 выводит вперёд high, и 5 возвращается.

Сложность

addNum: время O(log n), не больше двух добавлений и одного удаления. findMedian: время O(1), он только читает верхи. Память O(n) на все числа.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.