Ближайшие к базе точки

Средняя

База стоит в начале координат (0, 0). Дан список точек spots, где spots[i] = [x, y], и число count. Верните count точек, ближайших к базе по обычному (евклидову) расстоянию. Гарантируется, что набор ответа определён однозначно: точка на count-м месте по расстоянию строго ближе следующей. Точки можно вернуть в любом порядке.

Пример 1

spots=[[1, -2], [3, 0], [0, 1]], count=2 → [[0, 1], [1, -2]]

Квадраты расстояний до базы: 5, 9 и 1. Две ближайшие точки — [0, 1] и [1, -2].

Пример 2

spots=[[-4, 4], [2, 5]], count=1 → [[2, 5]]

16 + 16 = 32 против 4 + 25 = 29: точка [2, 5] чуть ближе.

Ограничения

1 ≤ count ≤ len(spots) ≤ 10⁴
-10⁴ ≤ x, y ≤ 10⁴
Набор из count ближайших точек единственный

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Geometry Array Math Divide and Conquer Quickselect Sorting Heap (Priority Queue)

Вход

spots=[[1, -2], [3, 0], [0, 1]], count=2

Ожидается

[[0, 1], [1, -2]]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 72 теста на сервере, включая скрытые.