最接近原点的 K 个点

难度: Medium

给定一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x₁ - x₂)² + (y₁ - y₂)² ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案确保是唯一的。

示例 1：

输入：points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]
解释： 
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

示例 2：

输入：points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

提示：

1 <= k <= points.length <= 10⁴
-10⁴ < x_i, y_i < 10⁴

Submission

运行时间: 90 ms

内存: 20.0 MB

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda x: x[0] ** 2 + x[1] ** 2)
        return points[:k]

Explain

这个题解的思路是直接对 points 数组按照每个点到原点的欧几里得距离进行排序，距离的计算公式是 x^2 + y^2。排序后取前 k 个点即为答案。这里利用了 Python 的 sort() 方法，通过 key 参数传入一个匿名函数实现自定义排序规则。

时间复杂度: O(nlogn)

空间复杂度: O(1)

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # 按照每个点到原点的欧几里得距离排序
        points.sort(key=lambda x: x[0] ** 2 + x[1] ** 2)
        
        # 取排序后的前 k 个点作为答案
        return points[:k]

Explore

在比较两个数的大小时，如果这两个数都是正数，则它们的平方关系和原始数的大小关系是一致的。因此，在计算点到原点的欧几里得距离时，可以直接比较它们到原点距离的平方和来避免进行平方根计算，这样可以减少计算量并提高效率。这种方法在所有情况下都是有效的，因为距离的平方和始终是非负的，而且比较的是相同的量度（平方和）。

直接对整个数组排序然后选择前k个元素是一种直观的解法，但不是最优的，因为其时间复杂度为O(n log n)。存在更高效的算法，如使用最大堆（或优先队列）来维护一个大小为k的数据结构。每次比较新元素与堆顶元素，如果新元素距离更小，则替换堆顶元素并重新调整堆。这种方法的时间复杂度为O(n log k)，在k远小于n的情况下更加高效。另一种方法是使用快速选择（Quickselect）算法，这可以在平均O(n)的时间内解决问题，但最坏情况仍然是O(n^2)。

在题目的上下文中，通常假定k不会大于n，因为k代表要返回的点的数量，而n是输入点的总数。如果k大于n，这在实际应用中意味着请求的返回数量超过了可用数据的数量。在实际编程实现中，应该添加一个检查来确保k不超过n，如果超过，可以返回全部点或者抛出一个错误提示，具体处理方式取决于问题的具体要求和预期的用途。

题解中的lambda函数假定列表中的元素是可以直接进行数学运算的数值型数据，例如整数或浮点数。如果输入的数据类型是字符串或其他非数值类型，则这个lambda函数将无法直接应用，因为进行平方运算前需要确保数据类型适合数学计算。在这种情况下，需要先将输入的数据转换成适合计算的类型（如从字符串转为整数或浮点数），或者在设计函数时就限定输入数据的类型，确保数据输入的一致性和正确性。