K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on a 2D plane and an integer k, return the k points that are closest to the origin (0, 0). You may return the answer in any order. The distance between two points on a plane is the Euclidean distance.
Constraints:
- 1 <= k <= points.length <= 10^4
- -10^4 < xi, yi < 10^4
Examples:
Input: [[1,3],[-2,2],[5,8],[0,1]], k = 2
Output: [[0,1],[-2,2]]
Explanation: The output depends on the Euclidean distance from the origin.
Solutions
Sorting
Time: O(n log n)Space: O(n)
This solution uses sorting to find the k closest points to the origin. The sorting key is the Euclidean distance from the origin.
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 a[0]*a[0] + a[1]*a[1] < b[0]*b[0] + b[1]*b[1];
}
);
return vector<vector<int>>(points.begin(), points.begin() + k);
}
}
;Follow-up:
What if the points are in 3D space?
