Commit95c3a7e

authored

973_K_Closest_Points_to_Origin

1 parent17051e6 commit95c3a7eCopy full SHA for 95c3a7e

File tree

+39

-0

lines changed

+39

-0

lines changed

Lines changed: 39 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,39 @@`
	`1`	`+classSolution {`
	`2`	`+/* public int[][] kClosest(int[][] points, int K) {`
	`3`	`+ // Sort`
	`4`	`+ int N = points.length;`
	`5`	`+ int[] dists = new int[N];`
	`6`	`+ for (int i = 0; i < N; ++i)`
	`7`	`+ dists[i] = dist(points[i]);`
	`8`	`+`
	`9`	`+ Arrays.sort(dists);`
	`10`	`+ int distK = dists[K-1];`
	`11`	`+`
	`12`	`+ int[][] ans = new int[K][2];`
	`13`	`+ int t = 0;`
	`14`	`+ for (int i = 0; i < N; ++i)`
	`15`	`+ if (dist(points[i]) <= distK)`
	`16`	`+ ans[t++] = points[i];`
	`17`	`+ return ans;`
	`18`	`+ } */`
	`19`	`+`
	`20`	`+privateintdist(int[]point) {`
	`21`	`+returnpoint[0] point[0] +point[1] point[1];`
	`22`	`+ }`
	`23`	`+`
	`24`	`+publicint[][]kClosest(int[][]points,intK) {`
	`25`	`+// Min Heap with PriorityQueue`
	`26`	`+PriorityQueue<int[]>pq =newPriorityQueue<int[]>((p1,p2) ->dist(p2) -dist(p1));`
	`27`	`+for (int[]p :points) {`
	`28`	`+pq.offer(p);`
	`29`	`+if (pq.size() >K) {`
	`30`	`+pq.poll();`
	`31`	`+ }`
	`32`	`+ }`
	`33`	`+int[][]res =newint[K][2];`
	`34`	`+while (K >0) {`
	`35`	`+res[--K] =pq.poll();`
	`36`	`+ }`
	`37`	`+returnres;`
	`38`	`+ }`
	`39`	`+}`

Comments

(0)