Kth closest points

Given an array containing N points, find the Kth closest points >to the origin in the 2D plane. You can assume K is much >smaller than N and N is very large.

Notice that the key requirement here are:”K is much smaller than N. N is very large.” Definitely the brute force solution by finding distance of all element and then sorting them in $O(nlogn)$ is not suitable. It is costlier as we don’t need to sort all the n points as we as only concerned for first k points in the sorted list. Based on the optimization principle of cracking the coding interview, we should deal with redundant work, unnecessary work and bottleneck during the process of optimizing an algorithm, we should take care of the sorting process here since we don’t actually need to make the distances in order.

An more efficient solution would be to use a Max-heap of size k for maintaining K minimum distances. Keep adding the distance value until the heap reaches size k. Since Max-heap has the nice property of popping out the largest one in $O(1)$ time, we could always replace the one with the largest distance with current point which has smaller distance. So the algorithm would be the following:
1. Keep adding distance value into the heap until it reaches size k.
2. If the distance of the new point is less than the current top element of the heap, replace the top element of the heap with the new distance. This is

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！