692. 前K个高频单词
- 题目
- 基础知识
- 代码
题目
给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。
示例 1:
输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 “i” 在 “love” 之前。
示例 2:
输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词,
出现次数依次为 4, 3, 2 和 1 次。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/top-k-frequent-words
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
基础知识
- 考虑到“键值对”并不是普通类型数据,C++ STL 标准库提供了 pair 类模板,其专门用来将 2 个普通元素 first 和 second(可以是 C++ 基本数据类型、结构体、类自定的类型)创建成一个新元素
。通过其构成的元素格式不难看出,使用 pair 类模板来创建“键值对”形式的元素,再合适不过。
直接使用 2 个元素初始化成 pair 对象
pair (const first_type& a, const second_type& b);
- auto 和 decltype 关键字都可以自动推导出变量的类型,但它们的用法是有区别的:其中,varname 表示变量名,value 表示赋给变量的值,exp 表示一个表达式。
auto 根据=右边的初始值 value 推导出变量的类型,而 decltype 根据 exp 表达式推导出变量的类型,跟=右边的 value 没有关系。
另外,auto 要求变量必须初始化,而 decltype 不要求。这很容易理解,auto 是根据变量的初始值来推导出变量类型的,如果不初始化,变量的类型也就无法推导了。decltype 可以写成下面的形式:
exp 注意事项
原则上讲,exp 就是一个普通的表达式,它可以是任意复杂的形式,但是我们必须要保证 exp 的结果是有类型的,不能是 void;例如,当 exp 调用一个返回值类型为 void 的函数时,exp 的结果也是 void 类型,此时就会导致编译错误。
auto varname = value;
decltype(exp) varname = value;
decltype(exp) varname;
代码
class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k) {std::unordered_map<string, int> count; //定义哈希表,用来存储每个单词出现多少次for (auto& word: words) {++count[word];}typedef pair<string, int> Node; //自定义一个比较函数 比较heap元素大小auto comp = [](const Node& a, const Node& b){if(a.second == b.second) return a.first <b.first;return a.second > b.second;};priority_queue<Node, vector<Node>, decltype(comp)> q(comp);//创建一个优先队列for(const auto& kv :count){q.push(kv);if (q.size()>k)q.pop();}vector<string> ans;while(!q.empty()){ans.push_back(q.top().first);q.pop();}std::reverse(ans.begin(),ans.end());return ans;}};










