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.
1import java.util.Arrays;
2
3class Solution {
4 public int[][] kClosest(int[][] points, int k) {
5 Arrays.sort(points, (a, b) -> (a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]));
6 return Arrays.copyOfRange(points, 0, k);
7 }
8}
9This Java solution uses Arrays.sort with a lambda function as a comparator to sort based on squared distances, then selects the subarray containing 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.
1using System.Collections.Generic;
public class Solution {
public int[][] KClosest(int[][] points, int k) {
PriorityQueue<int[], int> maxHeap = new PriorityQueue<int[], int>(Comparer<int>.Create((a, b) => b - a));
foreach (var point in points) {
int distSq = point[0] * point[0] + point[1] * point[1];
maxHeap.Enqueue(new int[]{point[0], point[1]}, distSq);
if (maxHeap.Count > k) {
maxHeap.Dequeue();
}
}
var result = new List<int[]>();
while (maxHeap.Count > 0) {
result.Add(maxHeap.Dequeue());
}
return result.ToArray();
}
}
This C# solution leverages the PriorityQueue to maintain a max-heap of the k closest points, organized by squared distances, using a custom comparator.