LinkedIn: K Nearest points on a plane

Question:
Given a list of points and a central point, find the k nearest points from the central point.

http://buttercola.blogspot.com/2015/11/linkedin-k-nearest-points-on-plane.html

Discussion

计算距离，维护一个大小为K的最小堆。典型的TOP K问题。Use a max heap. First store the first K points into the heap. Then compare the distance between the current point and the max point. If less than the max value, then poll out the max and add the current point into the heap.

Solution

class Point {
public:
    int x;
    int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
};

struct cmp {
    bool operator() (Point& A, Point& B) const {
        return A.x*A.x+A.y*A.y < B.x*B.x+B.y*B.y;
    }
};
bool cmparePoints(Point& A, Point& B) {
    return A.x*A.x+A.y*A.y < B.x*B.x+B.y*B.y;
}

vector<Point> findKClosest(vector<Point> p, int k) {
    if(p.size() < k) return vector<Point>();
    //create a max-heap with size k
    priority_queue<Point, vector<Point>, cmp> myheap(p.begin(), p.begin()+k);
    //maintain this max-heap
    for(int i=k; i<p.size(); i++) {
        if(comparePoints(p[i], myheap.top()) {
            myheap.pop();
            myheap.emplace(p[i]);
        }
    }
    //output nearest k points
    vector<Point> result;
    while(myheap.empty() == false) {
        result.emplace_back(myheap.top());
        heap.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}