973. K Closest Points to Origin
Difficulty: Medium
Related Topics: Divide and Conquer, Heap, Sort
We have a list of
points
on the plane. Find the
K
closest points to the origin
(0, 0)
.
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)
Note:
-
1 <= K <= points.length <= 10000
-
-10000 < points[i][0] < 10000
-
-10000 < points[i][1] < 10000
Solution
Language: Java
Key: Another way to use divide and conquer to reach only O(n) time complexity
class Solution {
public int[][] kClosest(int[][] points, int K) {
List<Point> result = new ArrayList<>();
int[][] res = new int[K][2];
Comparator<Point> comp = new Comparator<>() {
public int compare(Point a, Point b) {
return a.distance() - b.distance();
}
};
for (int i = 0; i < points.length; i ++) {
result.add(new Point(points[i][0], points[i][1]));
}
Collections.sort(result, comp);
for (int i = 0; i < K; i++) {
res[i][0] = result.get(i).x;
res[i][1] =result.get(i).y;
}
return res;
}
}
class Point {
int x;
int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
public int distance() {
return (x * x + y * y);
}
}