Medium

题目描述

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

X-Y 平面上两点间的距离是欧几里得距离（即，√(x1 - x2)² + (y1 - y2)²）。

你可以按任何顺序返回答案。答案保证是唯一的（除了顺序之外）。

示例 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⁴ <= xi, yi <= 10⁴

解题思路

这是一个经典的 Top K 问题，有多种解法：

方法1：排序 最直观的做法是计算所有点到原点的距离，然后排序取前 k 个。注意计算距离时可以不开方，因为比较大小时开方不影响结果。

方法2：堆（优先队列） 使用最小堆维护所有点的距离，然后弹出 k 次。或者使用最大堆维护 k 个最小的点，当堆大小超过 k 时弹出最大的。

方法3：快速选择（推荐） 基于快排的思想，使用快速选择算法可以在平均 O(n) 时间内找到第 k 小的元素。这是最优解法，特别适用于 k 相对较小的情况。

这里我们采用排序方法，代码简洁且易于理解。对于大数据集，可以考虑使用快速选择算法优化。

代码实现

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
        });
        return vector<vector<int>>(points.begin(), points.begin() + k);
    }
};

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

public class Solution {
    public int[][] KClosest(int[][] points, int k) {
        Array.Sort(points, (a, b) => {
            int distA = a[0] * a[0] + a[1] * a[1];
            int distB = b[0] * b[0] + b[1] * b[1];
            return distA.CompareTo(distB);
        });
        
        int[][] result = new int[k][];
        for (int i = 0; i < k; i++) {
            result[i] = points[i];
        }
        return result;
    }
}

var kClosest = function(points, k) {
    points.sort((a, b) => {
        const distA = a[0] * a[0] + a[1] * a[1];
        const distB = b[0] * b[0] + b[1] * b[1];
        return distA - distB;
    });
    return points.slice(0, k);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型排序解法
时间复杂度O(n log n)
空间复杂度O(1) 或 O(k)

说明：

  • 时间复杂度：排序需要 O(n log n) 时间
  • 空间复杂度：取决于排序算法的实现，原地排序为 O(1)，返回结果需要 O(k) 空间
  • 如果使用快速选择算法，时间复杂度可以优化到平均 O(n)

相关题目