This kinda blew my mind because we want the closest k elements, which means MIN distance, but we are still using a MAX Heap. Also, correct me if I am wrong, but looks like you computing the dist() every time you compare two elements in the priority queue. You can optimize this, by computing dist() for each point only once. Anyway, this is what I came up with: class Solution { class Point implements Comparable { int x; int y; int dist; Point(int x, int y) { this.x = x; this.y = y; this.dist = (x * x) + (y * y); } public int compareTo(Point p) { return p.dist - this.dist; } } public int[][] kClosest(int[][] points, int k) { PriorityQueue pq = new PriorityQueue(); for (int[] p : points) { Point pt = new Point(p[0], p[1]); pq.add(pt); if (pq.size() > k) { pq.remove(); } } int[][] ret = new int[k][2]; int num = 0; while (!pq.isEmpty()) { Point rem = pq.remove(); ret[num][0] = rem.x; ret[num][1] = rem.y; num++; } return ret; } }
@Amelia_jos
3 жыл бұрын
Pair of pair vector is redundant right? We could have simply used a custom comparator in sort function
@דנִיאל-צ8ק
3 жыл бұрын
After seeing your videos The logic becomes so easier that we don't need to see the code and we remember it. Keep going :)
@EricProgramming
3 жыл бұрын
Glad to hear that
@Adolphus386
3 жыл бұрын
If u have time please do a question on avl insertion and deletion sir.Atleast add to ur Queue.
@EricProgramming
3 жыл бұрын
I did a video in my data structure playlist call AVL Tree. Please have a look.
@Bjoern841
3 жыл бұрын
keep it up bro...solve medium and hard problems also bro.👍
Пікірлер: 13