Почему это работает
- В куче всегда k самых больших из уже пришедших чисел. Наверху — меньшее из них, а это и есть k-е по величине.
- Число меньше корня не попадёт в k самых больших ни сейчас, ни потом: числа только приходят и никуда не деваются. Поэтому оно входит в кучу и тут же уходит, как 3 здесь.
- Куча не вырастает больше k + 1, поэтому каждый add стоит O(log k), сколько бы чисел ни пришло до него.
Сложность
init: время O(n log n) для n чисел. Каждый add: время O(log k), одно добавление и не больше одного удаления. Память O(k) после init: в куче k чисел.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗