Sponsored
Sponsored
This approach leverages the simplicity of sorting the list of points based on their distance from the origin. After sorting, the first k points will be the closest ones. The key is to use the squared Euclidean distance to avoid the computational overhead of square root operations.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since the sorting is done in-place.
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
7 sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b) {
8 return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
9 });
10 return vector<vector<int>>(points.begin(), points.begin() + k);
11}
12This C++ solution uses the STL sort function with a custom comparator to sort the points by their squared distances, then selects the first k points.
The Max-Heap approach uses a priority queue to maintain the k closest points seen so far. By using a max-heap, we can efficiently insert new points and potentially evict the farthest point if it is further than any encountered point, leading to a reduced time complexity for finding the k closest points.
Time Complexity: O(n log k) since each insertion/extraction in the heap takes O(log k) time.
Space Complexity: O(k) for the heap storage.
1
This C solution maintains a max-heap of size k using a custom struct. It inserts each point by distance until the max-heap is full. For subsequent points, it compares distances and potentially evicts the farthest point if a closer point is found.