Untitled
unknown
plain_text
3 years ago
1.3 kB
6
Indexable
class Solution { public: int getDist(int x1, int y1, int x2, int y2){ return sqrt(pow(x2-x1, 2)+pow(y2-y1, 2)); } struct CMP{ bool operator()(pair<int, pair<int, int>> &p1, pair<int, pair<int, int>> &p2){ return p1.first<p2.first; }; }; vector<vector<int>> kClosest(vector<vector<int>>& points, int k) { vector<vector<int>> ans; int n= points.size(); priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int, int>>>, CMP> pq; // priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>, CMP> pq; map<pair<int, int>, int> mp; for(auto &point: points) mp[{point[0], point[1]}]= getDist(point[0], point[1],0,0); for( auto &x:mp){ if(pq.size()<k){ pq.push({x.second,{x.first.first, x.first.second}}); } else { if(pq.top().first<x.second){ pq.pop(); pq.push({x.second,{x.first.first, x.first.second}}); } } } while(!pq.empty()){ vector<int> tmp={pq.top().second.first, pq.top().second.second}; ans.push_back(tmp); pq.pop(); } return ans; } };
Editor is loading...