题目描述
We have a list of points
on the plane. Find the K
closest points to the origin (0, 0)
.
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)
Note:
1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000
题意:给一个点数组,求其中距离原点最近的$k$个点,可以以任意次序返回。
算法1
题解1:先排序,然后取前$k$个,时间复杂度$O(nlogn)$
算法2
(优先队列) $O(nlogk)$
C++ 代码
class Solution {
public:
struct node{
int x,y,idx;
node(int x,int y,int idx):x(x),y(y),idx(idx){}
bool operator< (const node &b) const
{
return x*x + y*y < b.x*b.x + b.y*b.y;
}
};
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
priority_queue<node> q;
int n = points.size();
vector<vector<int>> res(K);
for(int i = 0 ; i < K ; i ++)
q.push(node(points[i][0],points[i][1],i));
for(int i = K ; i < n ; i ++)
{
node cur = node(points[i][0],points[i][1],i);
if(cur < q.top())
{
q.pop();
q.push(cur);
}
}
int i = 0;
while(!q.empty())
{
res[i ++] = points[q.top().idx];
q.pop();
}
return res;
}
};
算法2
(分治) $O(n)$
题解3:上面两种方法都没有利用到一个重要的信息,就是我们需要返回的点次序是任意的。但是上面返回的$k$个点返回的次序是从小到大的,我们做了这么多额外的工作就必然会有额外的复杂度。
我们不妨考虑一下快速排序的原理,我们选择一个基准元素,然后将小于该基准元素的点都放在左边,然后将大于该基准元素都放在右边。类似的,如果我们选了一个基准点后,距离小于该基准点的元素恰好有$x$个,如果$x < k$那么说明我们还需要在右边区间找到$k - x -1$个元素,如果$x > k$,说明我们需要在左边区间找到$k$个元素。同样的思想我们可以用于找第$k$大的元素。
C++ 代码
class Solution {
public:
vector<vector<int>> res;
int dist(int x,int y)
{
return x * x + y * y;
}
void getKCloest(vector<vector<int>>& points,int l,int r,int K)
{
if(K <= 0) return;
if(r - l + 1 == K)
{
for(int t = l ; t <= r ; t ++)
res.push_back(points[t]);
return;
}
int flag = dist(points[l][0],points[l][1]);
int i = l,j = r;
while(i < j)
{
while(j > i && dist(points[j][0],points[j][1]) >= flag)
j --;
while(i < j && dist(points[i][0],points[i][1]) <= flag)
i ++;
if(i < j)
swap(points[i],points[j]);
}
swap(points[l],points[i]);
if(i - l < K)
{
for(int t = l ; t <= i ; t ++)
res.push_back(points[t]);
getKCloest(points,i + 1,r, K - (i - l + 1));
}else
{
getKCloest(points,l,i - 1,K);
}
}
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
getKCloest(points,0,points.size() - 1,K);
return res;
}
};
第二个快排会非常慢,C++还行,我用的python写的在超时的边缘徘徊,好像是因为有很多重复的点