大数据分析网站,网站建设设计主要系统,vps建设网站,wordpress最新文章模板文章目录1. 题目2. 解题2.1 排序2.2 优先队列2.3 快排思路1. 题目
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
#xff08;这里#xff0c;平面上两点之间的距离是欧几里德距离。#xff09;
你可以按任何顺序返回答案。除了…
文章目录1. 题目2. 解题2.1 排序2.2 优先队列2.3 快排思路1. 题目
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
这里平面上两点之间的距离是欧几里德距离。
你可以按任何顺序返回答案。除了点坐标的顺序之外答案确保是唯一的。
示例 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. 解题
类似题目LeetCode 215. 数组中的第K个最大元素快速排序
2.1 排序
class Solution {
public:vectorvectorint kClosest(vectorvectorint 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)进行排序前部分实现为堆
class Solution {
public:vectorvectorint kClosest(vectorvectorint 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 时间复杂度 O(nlogn)O(nlogn)O(nlogn)
2.2 优先队列
维持一个容量为K的大顶堆队列满了后续点比堆顶更接近原点时pop堆顶push当前点
struct cmp{bool operator()(const vectorint a, const vectorint b)const{return a[0]*a[0]a[1]*a[1] b[0]*b[0]b[1]*b[1];//大顶堆}
};
class Solution {
public:vectorvectorint kClosest(vectorvectorint points, int K) {if(K points.size())return points;priority_queuevectorint, vectorvectorint, 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]);}}vectorvectorint ans(q.size());int i 0;while(!q.empty()){ans[i] q.top();q.pop();}return ans;}
};时间复杂度 O(nlogK)O(nlogK)O(nlogK) 628 ms 47.5 MB
2.3 快排思路
class Solution {
public:vectorvectorint kClosest(vectorvectorint points, int K) {if(K points.size())return points;findkth(points,0,points.size()-1,K);points.resize(K);return points;}int dis(vectorvectorint points, int i){return points[i][0]*points[i][0]points[i][1]*points[i][1];}void findkth(vectorvectorint 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,i1,r,K);else if(i K)//左边多于K个在左边继续分割findkth(points,l,i-1,K);elsereturn;}
};时间复杂度 O(n)O(n)O(n) 244 ms 39 MB
