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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 int *pointA = *(int **)a;
6 int *pointB = *(int **)b;
7 int distA = pointA[0] * pointA[0] + pointA[1] * pointA[1];
8 int distB = pointB[0] * pointB[0] + pointB[1] * pointB[1];
9 return distA - distB;
10}
11
12int** kClosest(int** points, int pointsSize, int* pointsColSize, int k, int* returnSize, int** returnColumnSizes) {
13 qsort(points, pointsSize, sizeof(int*), compare);
14 *returnSize = k;
15 *returnColumnSizes = (int *)malloc(sizeof(int) * k);
16 for (int i = 0; i < k; i++) {
17 (*returnColumnSizes)[i] = 2;
18 }
19 return points;
20}
21This C code uses the qsort function to sort the points array based on the calculated squared distances. It extracts the first k elements and returns them as the closest 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#include <queue>
#include <cmath>
using namespace std;
typedef pair<int, vector<int>> pdvi;
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
priority_queue<pdvi> maxHeap;
for (auto& p : points) {
int dist = p[0] * p[0] + p[1] * p[1];
maxHeap.push({dist, p});
if (maxHeap.size() > k) {
maxHeap.pop();
}
}
vector<vector<int>> result;
while (!maxHeap.empty()) {
result.push_back(maxHeap.top().second);
maxHeap.pop();
}
return result;
}
This C++ solution uses a priority queue (max-heap) containing tuples of (distance, point). It maintains the k closest points by removing the point with the largest distance when the heap exceeds size k.