The k Points Nearest the Origin
Problem statement
You are given a list of points on a plane, points[i] = [x, y], and an integer k. Return the k points closest to the origin [0, 0], using the usual straight-line distance sqrt(x^2 + y^2).
Return them in order: closest first. If two points are equally far, the one with the smaller x comes first, and if x is also equal, the smaller y. A point that appears twice in the list counts as two points.
Function
kClosestPoints(points: int[][], k: int) → int[][]Examples
Example 1
points = [[2,2],[-1,1],[0,3],[1,-1]]k = 2return = [[-1,1],[1,-1]]The squared distances are 8, 2, 9 and 2. The two closest points, [-1, 1] and [1, -1], tie at 2, so the smaller x comes first.
Example 2
points = [[5,0],[0,5],[0,-5],[-5,0]]k = 3return = [[-5,0],[0,-5],[0,5]]All four points are at distance 5. Ordered by x and then y they are [-5, 0], [0, -5], [0, 5], [5, 0]; the first three are returned.
Example 3
points = [[7,7]]k = 1return = [[7,7]]Only one point, so it is returned.
Constraints
1 <= k <= points.length <= 3000points[i].length == 2-10^4 <= x, y <= 10^4