[LintCode] K Closest Points
Given some points and a point origin in two dimensional space, find k points out of the some points which are nearest to origin.Return these points sorted by distance, if they are same with distance, sorted by x-axis, otherwise sorted by y-axis.
Example
Given
points = [[4,6],[4,7],[4,4],[2,5],[1,1]]
, origin = [0, 0]
, k = 3
return [[1,1],[2,5],[4,4]]
Solution
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
/*
* @param points: a list of points
* @param origin: a point
* @param k: An integer
* @return: the k closest points
*/
public Point[] kClosest(Point[] points, Point origin, int k) {
Comparator pointComparator = new Comparator() {
public int compare(Point A, Point B) {
if (distance(B, origin) == distance(A, origin)) {
if (A.x == B.x) {
return A.y - B.y;
} else {
return A.x - B.x;
}
} else {
//maintain a min heap
return distance(A, origin) > distance(B, origin) ? 1 : -1;
}
}
};
PriorityQueue Q = new PriorityQueue(k, pointComparator);
for (Point point: points) {
Q.add(point);
}
Point[] res = new Point[k];
for (int i = 0; i < k; i++) {
res[i] = Q.poll();
}
return res;
}
public double distance(Point A, Point B) {
int l = Math.abs(A.x - B.x);
int w = Math.abs(A.y - B.y);
return Math.sqrt(Math.pow(l, 2) + Math.pow(w, 2));
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
프랙탈 모양 그리기 (Koch 곡선)어쨌든 Koch 곡선은 이러한 "자기 유사성"을 가진 도형입니다. 그리는 방법의 단계는 다음과 같습니다. 이 선을 3등분하고, 중간의 직선의 가장자리를 2정점으로 하는 정삼각형을 그린다 수작업은 물론, 프로그램에서도...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.