1. 题目
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
代码语言：javascript复制示例 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 <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/k-closest-points-to-origin 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 排序
代码语言：javascript复制class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
if(K == points.size())
return points;
sort(points.begin(),points.end(),[&](auto a, auto b){
return a[0]*a[0] a[1]*a[1] < b[0]*b[0] b[1]*b[1];
});
points.resize(K);
return points;
}
};1772 ms 191.6 MB
partial_sort 只对前部分[first,middle)进行排序，前部分实现为堆
代码语言：javascript复制class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
partial_sort(points.begin(), points.begin() K, points.end(), [&] (auto a, auto b){
return a[0]*a[0] a[1]*a[1] < b[0]*b[0] b[1]*b[1];
});
points.resize(K);
return points;
}
};1552 ms 148.4 MB 时间复杂度
2.2 优先队列
- 维持一个容量为K的大顶堆
- 队列满了，后续点比堆顶更接近原点时，pop堆顶，push当前点
struct cmp{
bool operator()(const vector<int>& a, const vector<int>& b)const
{
return a[0]*a[0] a[1]*a[1] < b[0]*b[0] b[1]*b[1];//大顶堆
}
};
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
if(K == points.size())
return points;
priority_queue<vector<int>, vector<vector<int>>, cmp> q;
for(int i = 0; i < points.size(); i)
{
if(q.size() < K)
q.push(points[i]);
else if(q.top()[0]*q.top()[0] q.top()[1]*q.top()[1] >
points[i][0]*points[i][0] points[i][1]*points[i][1])
{
q.pop();
q.push(points[i]);
}
}
vector<vector<int>> ans(q.size());
int i = 0;
while(!q.empty())
{
ans[i ] = q.top();
q.pop();
}
return ans;
}
};时间复杂度
628 ms 47.5 MB
2.3 快排思路
代码语言：javascript复制class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
if(K == points.size())
return points;
findkth(points,0,points.size()-1,K);
points.resize(K);
return points;
}
int dis(vector<vector<int>>& points, int i)
{
return points[i][0]*points[i][0] points[i][1]*points[i][1];
}
void findkth(vector<vector<int>>& points,int l, int r, int K)
{
int i = l, j = r, p = dis(points, l);
while(i < j)
{
while(i < j && dis(points,j) > p)//必须先从右边开始，因为选的pivot在左边
j--;
while(i < j && dis(points,i) <= p)
i ;
swap(points[i], points[j]);
}
swap(points[l], points[i]);
if(i < K)//左边都是答案的一部分，取右边找
findkth(points,i 1,r,K);
else if(i > K)//左边多于K个，在左边继续分割
findkth(points,l,i-1,K);
else
return;
}
};时间复杂度
244 ms 39 MB
