c++ - 查找前K个频繁词

Question

我正在尝试解决来自 Leetcode 网站的问题 - Finding top K frequent words .

Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first. E.g.: if the input is: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4, then the output should be: ["the", "is", "sunny", "day"].

其中一个被赞成的解决方案如下所示:

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> dict;
        for(const string& s:words) dict[s]++;

        priority_queue<pair<string,int>, vector<pair<string,int>>, Comp> pq;
        for(const auto& pa:dict) {
            pq.push(pa);
            if(pq.size()>k) pq.pop();
        }    

        vector<string> result;
        while(!pq.empty()) {
            result.push_back(pq.top().first);
            pq.pop();
        }
        reverse(result.begin(),result.end());    
        return result;    
    }
private:
    struct Comp {
        Comp() {}
        ~Comp() {}
        bool operator()(const pair<string,int>& a, const pair<string,int>& b) {
            return a.second>b.second || (a.second==b.second && a.first<b.first);
        }
    };

};

我试图更好地理解它并有几个问题:

1. 何时pq.size()>k , 我们 pop() - 这不是不正确吗，因为在那种情况下我们会丢失最高频率的元素？我认为是这样，因为根据比较器，具有较高频率(或在相同频率的情况下按字母顺序较小)的元素被插入到优先级队列的顶部。
2. 在优先队列的情况下，当我们实现自己的比较器时，我们必须传递第二个参数(表示要使用的容器)，但在我们使用默认比较器时不需要 - 为什么这样？我的意思是，不能根据我要存储的值的类型(第一个参数，在本例中为 pair<string, int> )自动推导默认容器类型吗？
3. 如果是pq.push(pa); , pa 的类型到底是什么？我想知道因为pq包含 vector<pair<string, int>> ，但是 dict只包含 string (映射到它们在 int 中的频率)。如何使用 auto自动映射 string其int的关键插入优先级队列的频率？

很抱歉回答这么长的问题。并感谢您的帮助。

Answer 1

1. 您并没有真正取出频率最高的那些，因为顺序被颠倒到优先级队列中。事实上，最后有一个反向调用以正确 顺序输出元素。请注意，文档中是否明确说明了这一点。

来自 docs

Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare.

1. pa 的类型是 unordered_map<string,int>::value_type 中指定的类型这是 std::pair<const string,int> . 事实上 unordered_map<K, V>::value_type 的每个元素, 是 std::pair<const K, V> 的类型定义自 priority_queue商店 std::pair<string,int>没有发生奇怪的事情。

希望这对您有所帮助。