Untitled

 avatar
unknown
plain_text
15 days ago
1.2 kB
3
Indexable
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