Выбор ответа Senior Куча обновлено
Медиана потока
Вопрос
Числа приходят по одному, после каждого нужно отвечать медианой. Какая структура?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Max-куча для нижней половины и min-куча для верхней. Вершины двух куч это середина данных.
Варианты ответа
- Отсортированный массив со вставкой бинпоиском, O(log n)
- Одна min-куча, медиана берётся из её середины
- Хеш-таблица частот с подсчётом по ключам
- Max-куча для нижней половины и min-куча для верхнейправильный ответ
Разбор
Вершины двух куч это середина данных. Вставка O(log n) с перебалансировкой, медиана O(1).
- Бинпоиск найдёт место за O(log n), но вставка в массив сдвигает элементы: O(n).
- Одна куча даёт только минимум.
- Частоты не дают порядок без сортировки.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.