在下面的代码中,当在优先级队列中使用时,比较项是被推送的项目吗? 因此,在Mycomp
函数中,pair &a
要添加的对象和pair &b
,是否已经在队列中并与之进行比较?
class Solution {
public:
struct Mycomp {
bool operator()(const pair<int, string> &a, const pair<int, string> &b){
if(a.first != b.first) { // comparing the frequency if it is not same then return the one with smallest frequency
return a.first > b.first;
}else{
// if frequency are same then compare the alphabetical order - should return the largest one as the idead is to pop smallest frequency with
// largest alphabetical order
return a.second < b. second;
}
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
//defining a map to keep track of the frequency of the words
std::unordered_map<string, int> hashMap;
for( auto word : words) {
hashMap[word]++;
}
// Now we use the concept of priority queue
std::priority_queue<pair<int, string>,std::vector<pair<int,string>>, Mycomp> pq ;
for(auto ele : hashMap) {
pq.push({ele.second, ele.first});
if(pq.size() > k) {
pq.pop(); // pop the elements with least frequency
}
}
vector<string> result;
while(k--){
result.insert(result.begin(),pq.top().second); // if you use push back, then you need to reverse the vector as pq returns the highest alpabetical order when popping.
pq.pop();
}
return result;
}
};
No.第一个参数不是要添加的对象。
operator()
的第二个参数,通常是刚刚添加的对象。
通常,第一个参数是队列的中间元素。
但同样,在某些情况下,这些行为有可能出乎意料,并且取决于所使用的编译器或算法。