为什么我把pq也存成（元素，频次）就不对，make_pair和res.push_back里都做了相应调整
来源：6-7 优先队列相关的算法问题 Top K Frequent Elements
幕布斯0154384
2018-08-07
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
assert(k>0);
unordered_map<int,int> record;
for(int i=0; i<nums.size(); i++)
record[nums[i]]++;
assert(k <= record.size());
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
for(unordered_map<int,int>::iterator iter=record.begin(); iter != record.end(); iter++){
if(pq.size() == k){
if(iter->second > pq.top().second){
pq.pop();
pq.push(make_pair(iter->first, iter->second));
}
}
else
pq.push(make_pair(iter->first, iter->second));
}
vector<int> res;
while(!pq.empty()){
res.push_back(pq.top().first);
pq.pop();
}
return res;
}
};
1回答
-
liuyubobobo
2018-08-07
首先，课程所讲解的算法，是按照（频次，元素）的顺序进行存储的。这一小节的课程官方代码，请参考：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/06-Stack-and-Queue/Course%20Code%20(C%2B%2B)/07-Top-K-Frequent-Elements/main.cpp
为什么使用（元素，频次）存储是不对的？因为C++中，两个pair类型比较，默认是先比较第一个元素，再比较第二个元素的。所以如果使用（频次，元素）存储，将先比较频次，从而达到每次从堆中取出频次最大的元素的目的。但是如果按照（元素，频次）存储，每次从对中取出的是元素的值最大的这个数据对，根本没有根据元素的频次取出数据，结果肯定是不对的：）
如果愿意，可以debug但不跟踪试试看。对于一个小的测试用例，看看按照（频次，元素）存储和按照（元素，频次）存储，每次从优先队列取出的数据有什么不同？：）
加油！
10
相似问题