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