0973. K Closest Points to Origin

题目信息

题号:

0973

难度:

Medium

主题:

平面点集、欧几里得距离、选取最近点

原题:

LeetCode 0973

重点:

距离按原点的欧几里得距离比较;返回恰好 k 个最近点,答案点集由输入保证唯一,仅返回顺序可以不同

题目重述

给定平面点数组 points,其中 points[i] = [x_i, y_i],以及整数 k。点到原点 (0, 0) 的距离为 sqrt(x_i^2 + y_i^2)。

请返回距离原点最近的 k 个点。题目保证最近点集合是唯一的,但这些点在结果中的排列顺序不限。

1 <= k <= points.length <= 10^4,-10^4 <= x_i, y_i <= 10^4。

自建示例

按平方距离选择两个点:

输入:points = [[2,0],[1,1],[-1,0]], k = 2
输出:[[-1,0],[1,1]]
解释:三个点的平方距离分别为 4、2、1,因此最近的两个点是 [-1,0] 和 [1,1]。输出顺序可以不同。

需要返回全部输入点:

输入:points = [[3,4],[-2,0]], k = 2
输出:[[3,4],[-2,0]]
解释:k 等于点的总数,两个输入点都必须返回,结果顺序不限。