Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.3 kB
2
Indexable
Never
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;
    }
};