下面是从数组中获取前K个频繁元素的代码。代码是正确的,但我对比较器在这里做什么感到困惑。为什么是"p1.秒
class Solution {
struct compare {
bool operator() (pair<int, int>p1, pair<int, int>p2) {
return p1.second > p2.second;
}
};
public:向量topK频繁(向量
int n = nums.size();
unordered_map<int, int>m;
for (int i = 0; i < n; i++) {
m[nums[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, compare>pq;
for (auto it = m.begin(); it != m.end(); it++) {
pq.push(make_pair(it->first, it->second));
if (pq.size() > k)
pq.pop();
}
vector<int>v;
while (!pq.empty()) {
pair<int, int>p = pq.top();
v.push_back(p.first);
pq.pop();
}
return v;
**}
};**
默认情况下,std::priority_queue使用std::less比较器。在这种情况下,pop()
删除最大的元素。
但是,在您的情况下,您希望将k
最大的元素保留在队列中,而pop()
最小的元素(丢弃它)。为此,您需要颠倒比较的意义。
优先级队列所做的是在容器上构建一个堆,容器的尾部是堆的顶部,
当我们想要以自定义的方式构建堆时,比较器函数作为参数传递。堆的一个节点存储两个值,元素及其频率。由于您使用的是对