寻找出现频率前K高的单词

Question

寻找出现频率前K高的单词

4

我正在尝试解决来自Leetcode网站的问题 - 找到前K个高频单词。

给定一个非空单词列表，返回出现频率最高的k个元素。您的答案应按频率从高到低排序。如果两个单词具有相同的频率，则较低字母顺序的单词先出现。例如：如果输入为：["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"]，k = 4，则输出应为：["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);
        }
    };

};

我正在努力理解它，并有一些问题：

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

非常抱歉问题这么长。感谢您的帮助。

- user6490375

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Davide Spataro · Accepted Answer

你并没有真正地取出最高频率的元素，因为列表是反向排序进入优先队列的。实际上，在最后有一个 reverse 调用来按照正确的顺序输出元素。请注意，这在文档中已经明确说明了。

来源于 docs

请注意，比较参数被定义为，如果它的第一个参数在弱序中排在第二个参数之前，则返回 true。但是由于优先队列首先输出最大的元素，因此“排在前面”的元素实际上是最后输出的。也就是说，队列的前面包含了根据 Compare 强制执行的弱序中的“最后”元素。

pa 的类型是在 unordered_map<string,int>::value_type 中指定的类型，即 std::pair<const string,int>。实际上，unordered_map<K, V>::value_type 的每个元素都是一个 typedef，代表 std::pair<const K, V>。由于 priority_queue 存储的是 std::pair<string,int>，因此不会发生奇怪的事情。

希望这可以帮助你。