leetcode692，这个优先队列到底是怎么用的？

Question

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> res(k);
        unordered_map<string, int> freq;
        auto cmp = [](pair<string, int>& a, pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        //这里，我在csdn中找的别的例子一般也就是把函数单独写出来然后放着里。为什么会用到decltype呢？为什么q后面也要写(cmp)呢？C++reference中也没找到相关的例子
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp) > q(cmp);
        for (auto word : words) ++freq[word];
        for (auto f : freq) {
            q.push(f);
            if (q.size() > k) q.pop();
        }
        for (int i = res.size() - 1; i >= 0; --i) {
            res[i] = q.top().first; q.pop();
        }
        return res;
    }
};

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

这是一个使用优先队列（priority queue）来解决频繁出现单词的问题。在这个问题中，我们有一个vector words，其中存储了我们需要查找的单词列表。我们还需要一个整数 k，代表我们要找出频率最高的 k 个单词。

首先，我们初始化了一个大小为 k 的数组 res 来存放结果。

接下来，我们将一个名为 cmp 的函数声明为 decltype(cmp)，这表明我们可以使用 lambda 函数作为比较器。lambda 函数用于根据单词的频率对单词进行排序。

在 for 循环中，我们遍历 words 中的每个单词，并将其添加到优先队列 q 中。当队列中的元素数量超过 k 时，我们从队列中删除最小的元素（即频率最高的单词），以保持队列的大小为 k。

最后，在 for 循环结束后，我们通过反转 res 数组的顺序来得到结果，因为我们在 for 循环中是从后向前迭代的。

以下是完整的代码：

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> res(k);
        unordered_map<string, int> freq;
        auto cmp = [](pair<string, int>& a, pair<string, int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };

        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> q(cmp);

        for (auto word : words) ++freq[word];

        for (auto f : freq) {
            q.push(f);
            if (q.size() > k) q.pop();
        }

        for (int i = res.size() - 1; i >= 0; --i) {
            res[i] = q.top().first; q.pop();
        }

        return res;
    }
};

请注意，这段代码是 C++ 实现的，如果您使用的是其他编程语言，请确保将代码和示例转换为您正在使用的语言的语法。