Сложность: medium
Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).
Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).
Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка).
Пример:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
👨💻 Алгоритм:
1⃣Отсортируйте массив с помощью функции компаратора.
2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.
3⃣Верните первые k элементов массива.
😎 Решение:
class Solution:
def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
points.sort(key=self.squaredDistance)
return points[:k]
def squaredDistance(self, point: list[int]) -> int:
return point[0] ** 2 + point[1] ** 2
Ставь 👍 и забирай 📚 Базу знаний