Почему это работает
- В куче всегда k ближайших из прочитанных точек. Её корень — самая дальняя из них, поэтому новая точка попадает в кучу ровно тогда, когда она ближе корня.
- Это k наибольших с карточки, только наоборот: для k самых маленьких расстояний куча держит наверху самое большое — то, что уходит первым.
- x² + y² растёт вместе с самим расстоянием, поэтому сравнение квадратов даёт тот же порядок, и корень извлекать не нужно.
Сложность
Время O(n log k): каждая из n точек стоит не больше одного удаления и одного добавления в куче из k. Память O(k) на кучу.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗