Top k问题
程序员文章站
2024-03-15 21:38:36
...
#include <vector>
#include <queue>
using namespace std;
class Solution {
//比较结构体 Functional
struct cmp {
bool operator()(pair<int, int>&a, pair<int, int>&b) {
return a.first*a.first + a.second*a.second < b.first*b.first + b.second*b.second;
}
};
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
vector<vector<int>>res;
//定义:priority_queue<Type, Container, Functional>
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp>q;
for (int i = 0; i < points.size(); i++) {
pair<int, int>x;
x.first = points[i][0];
x.second = points[i][1];
q.push(x);
if (q.size() > K) q.pop();
}
while (!q.empty()) {
res.push_back({ q.top().first,q.top().second });
q.pop();
}
return res;
}
};
class Solution1 {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
sort(points.begin(), points.end(), cmp); //先对数组排序
return vector<vector<int>>(points.begin(), points.begin() + K); //输出前K位
}
static bool cmp(vector<int>&a, vector<int>&b) { //排序方法
return sqrt(pow(a[0], 2) + pow(a[1], 2)) < sqrt(pow(b[0], 2) + pow(b[1], 2));
}
};
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
sort(points.begin(), points.end(), [](const vector<int> &a, const vector<int> &b) {return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1]; });
return vector<vector<int>>(points.begin(), points.begin() + K);
}