Выбор ответа Middle Куча спрашивают часто обновлено
k наибольших элементов
Вопрос
Нужно найти k наибольших из n чисел, k много меньше n. Какой подход лучше сортировки?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Min-куча размера k с заменой вершины, O(n log k). Min-куча держит k лучших, а в вершине худший из них.
Варианты ответа
- Max-куча из всех n элементов и k извлечений, O(n log n)
- Сортировка, O(n log n), быстрее для этой задачи нельзя
- Min-куча размера k с заменой вершины, O(n log k)правильный ответ
- Два указателя с концов массива после разбиения
Разбор
Min-куча держит k лучших, а в вершине худший из них. Новый элемент либо отбрасывается за O(1), либо заменяет вершину за O(log k). Итого O(n log k), память O(k).
- Max-куча из всех построится за O(n) через heapify, но вставками это O(n log n), и память O(n).
- Сортировка работает, но O(n log n) хуже при малом k.
- Два указателя не находят k максимумов.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.