【leetcode】973. 最接近原点的 K 个点（k-closest-points-to-origin）（模拟）[中等]

链接

https://leetcode-cn.com/problems/k-closest-points-to-origin/

耗时

解题：21 min
题解：5 min

题意

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

（这里，平面上两点之间的距离是欧几里德距离。）

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

思路

计算每个点和原点的距离，然后按距离排序，取前 K 个。

时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)

AC代码

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        vector<pair<int, int>> dis;
        int n = points.size();
        for(int i = 0; i < n; ++i) {
            auto point = points[i];
            int d = point[0]*point[0]+point[1]*point[1];
            dis.push_back(make_pair(d, i));
        }
        sort(dis.begin(), dis.end());
        vector<vector<int>> ans;
        for(int i = 0; i < K; ++i) {
            int pos = dis[i].second;
            ans.push_back({points[pos][0], points[pos][1]});
        }
        return ans;
    }
};