Untitled
import java.util.PriorityQueue; public class ClosestPoints { public static int[][] kClosest(int[][] points, int k) { // Max-Heap to store points based on their negative squared distance PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1])); for (int[] point : points) { maxHeap.add(point); if (maxHeap.size() > k) { maxHeap.poll(); // Remove the farthest point } } // Collect the k closest points from the heap int[][] result = new int[k][2]; for (int i = 0; i < k; i++) { result[i] = maxHeap.poll(); } return result; } public static void main(String[] args) { int[][] points = {{1, 3}, {-2, 2}, {5, 8}, {0, 1}}; int k = 2; int[][] closest = kClosest(points, k); System.out.println("The " + k + " closest points to the origin are:"); for (int[] point : closest) { System.out.println("[" + point[0] + ", " + point[1] + "]"); } } }
Leave a Comment