Код Senior Память и производительность обновлено
Скользящая медиана потока на двух кучах
Условие
Напишите running_median(stream): после каждого числа потока верните текущую медиану (для чётного количества полусумму двух средних как float, для нечётного число как есть). Каждый шаг O(log n).
Примеры
running_median([5, 15, 1, 3]) // [5, 10, 5, 4]
running_median([]) // []
running_median([7]) // [7]
Как подойти
Подсказки: 2
- Макс-куча в
heapq: храните-x. - Разница размеров куч не больше одного.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.