Thursday, November 19, 2015

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.

Solution:
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.

Code (Java):
public class Solution {
    public List<Point> findKNearestPoints(List<Point> points, Point original, int k) {
        List<Point> result = new ArrayList<>();
        
        if (points == null || ponts.size() == 0 || original == null || k <= 0) {
            return result;
        }
        
        PriorityQueue<Point> pq = new PriorityQueue<>(k);
        
        for (Point point : points) {
            if (pq.size() < k) {
                pq.offer(point);
            } else {
                if (pq.peek().compareTo(point) > 0) {
                    pq.poll();
                    pq.offer(point);
                }
            }
        }
        
        result.addAll(pq);
        return result;
    }
    
    class Point implements Comparable<Point> {
        int x, y;
        double distance;
        
        public Point (int x, int y, Point original) {
            this.x= x;
            this.y = y;
            
            // sqrt(x^2 + y^2)
            distance = Math.hypot(x - original.x, y - original.y);
        }
        
        @Override
        public int compareTo(Point that) {
            return this.distance.compareTo(that.distance);
        }
    }
}



其他参考答案:
http://yuanhsh.iteye.com/blog/2192675

Max Heap: O(NlogN)
Selection Algorithm: O(N)
下面给出基于Max Heap的实现。

Code (Java):
/*
public class Point {
    public int x;
    public int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
*/
 
public List<Point> findKClosest(Point[] p, int k) {
    PriorityQueue<Point> pq = new PriorityQueue<>(10, new Comparator<Point>() {
        @Override
        public int compare(Point a, Point b) {
            return (b.x * b.x + b.y * b.y) - (a.x * a.x + a.y * a.y);
        }
    });
     
    for (int i = 0; i < p.length; i++) {
        if (i < k)
            pq.offer(p[i]);
        else {
            Point tmp = pq.peek();
            if ((p[i].x * p[i].x + p[i].y * p[i].y) - (tmp.x * tmp.x + tmp.y * tmp.y) < 0) {
                pq.poll();
                pq.offer(p[i]);
            }
        }
    }
     
    List<Point> x = new ArrayList<>();
    while (!pq.isEmpty())
        x.add(pq.poll());
     
    return x;
}



1 comment:

  1. Max heap应该是that.distance.compareTo(this.distance)吧?然后line 15应该是<0?

    ReplyDelete