Non-Leetcode Questions: k-Nearest Points to Origin
Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large.
O(nlogk)
public List<Point> kNearestToOrigin(List<Point> set, int k){
Comparator<Point> comparator = new Comparator<Point>(){
@Override
public int compare(Point a, Point b){
if(Math.pow(a.x,2)+Math.pow(a.y,2) > Math.pow(b.x,2)+Math.pow(b.y,2))
return -1;
else if(Math.pow(a.x,2)+Math.pow(a.y,2) < Math.pow(b.x,2)+Math.pow(b.y,2))
return 1;
else
return 0;
}
};
List<Point> rlst = new ArrayList<Point>();
PriorityQueue<Point> heap = new PriorityQueue<Point>(set.size(), comparator);
for(int i = 0;i < k && i < set.size();i++)
heap.add(set.get(i));
for(int i = k;i < set.size();i++){
if(comparator.compare(set.get(i),heap.peek()) > 0){
heap.poll();
heap.add(set.get(i));
}
}
while(!heap.isEmpty()){
rlst.add(heap.poll());
}
return rlst;
}
Read full article from Non-Leetcode Questions: k-Nearest Points to Origin
Find the K closest points to the origin in 2D plane, given an array containing N points. You can assume K is much smaller than N and N is very large.
O(nlogk)
public List<Point> kNearestToOrigin(List<Point> set, int k){
Comparator<Point> comparator = new Comparator<Point>(){
@Override
public int compare(Point a, Point b){
if(Math.pow(a.x,2)+Math.pow(a.y,2) > Math.pow(b.x,2)+Math.pow(b.y,2))
return -1;
else if(Math.pow(a.x,2)+Math.pow(a.y,2) < Math.pow(b.x,2)+Math.pow(b.y,2))
return 1;
else
return 0;
}
};
List<Point> rlst = new ArrayList<Point>();
PriorityQueue<Point> heap = new PriorityQueue<Point>(set.size(), comparator);
for(int i = 0;i < k && i < set.size();i++)
heap.add(set.get(i));
for(int i = k;i < set.size();i++){
if(comparator.compare(set.get(i),heap.peek()) > 0){
heap.poll();
heap.add(set.get(i));
}
}
while(!heap.isEmpty()){
rlst.add(heap.poll());
}
return rlst;
}
Read full article from Non-Leetcode Questions: k-Nearest Points to Origin
