Сложность: 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 {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
sort(points.begin(), points.end(), [&](vector<int>& a, vector<int>& b) {
return squaredDistance(a) < squaredDistance(b);
});
return vector<vector<int>>(points.begin(), points.begin() + k);
}
private:
int squaredDistance(vector<int>& point) {
return point[0] * point[0] + point[1] * point[1];
}
};Ставь 👍 и забирай 📚 Базу знаний