692.前k个高频单词（堆优先队列）

链接：692. 前K个高频单词 - 力扣（LeetCode）

题解：

push进入que中，不能只比较count，还需要比较字符串字典序列，所以要用node类型进行比较

class Solution { public: struct Node { Node(string s, int c) { word = s; count = c; } bool operator<(const Node& n) const { if (count > n.count) { // 约大的在下面 return true; } else if (count == n.count && word < n.word) { // 字典许约小的在下面 return true; } return false; } int count; string word; }; vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> table; for (auto& w : words) { ++table[w]; } priority_queue<Node, vector<Node>> que; for (auto& e : table) { Node node(e.first, e.second); if (que.size() < k) { que.push(node); } else if (!que.empty() && node < que.top() ) { que.pop(); que.push(node); } /*if (que.size() >= k) { Node node(e.first, e.second); que.push(node); // 先压入在弹出 que.pop(); } else { Node node(e.first, e.second); que.push(node); }*/ } vector<string> result; result.resize(k); for (int i = k - 1; i >= 0; --i) { result[i] = que.top().word; que.pop(); } /*result.reserve(k); while (!que.empty()) { result.push_back(que.top().word); que.pop(); }*/ //reverse(result.begin(), result.end()); return result; } };

class Solution { public: struct Node { Node(string s, int c) { word = s; count = c; } bool operator<(const Node& n) const { if (count > n.count) { // 约大的在下面 return true; } else if (count == n.count && word < n.word) { // 字典许约小的在下面 return true; } return false; } int count; string word; }; vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> table; for (auto& w : words) { ++table[w]; } priority_queue<Node, vector<Node>> que; for (auto& e : table) { Node node(e.first, e.second); que.push(node); if (que.size() > k) { que.pop(); } /*if (que.size() >= k) { Node node(e.first, e.second); que.push(node); // 先压入在弹出 que.pop(); } else { Node node(e.first, e.second); que.push(node); }*/ } vector<string> result; result.resize(k); for (int i = k - 1; i >= 0; --i) { result[i] = que.top().word; que.pop(); } /*result.reserve(k); while (!que.empty()) { result.push_back(que.top().word); que.pop(); }*/ //reverse(result.begin(), result.end()); return result; } };

class Solution { public: struct Node { Node(string s, int c) { word = s; count = c; } bool operator<(const Node& n) const { if (count > n.count) {// 约大的在下面 return true; } else if (count == n.count && word < n.word) { // 字典许约小的在下面 return true; } return false; } int count; string word; }; vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> table; for (auto& w : words) { ++table[w]; } priority_queue<Node> que; for (auto& e : table) { if (que.size() >= k) { Node node(e.first, e.second); que.push(node); // 先压入在弹出 que.pop(); } else { Node node(e.first, e.second); que.push(node); } } vector<string> result; result.reserve(k); while (!que.empty()) { result.push_back(que.top().word); que.pop(); } reverse(result.begin(), result.end()); return result; } };

class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> cnt; for (auto& word : words) { cnt[word]++; } auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) { return a.second == b.second ? a.first < b.first : a.second > b.second; }; priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp); for (auto& it : cnt) { que.emplace(it); if (que.size() > k) { que.pop(); } } vector<string> ret(k); for (int i = k - 1; i >= 0; i--) { ret[i] = que.top().first; que.pop(); } return ret; } }; 作者：力扣官方题解 链接：https://leetcode.cn/problems/top-k-frequent-words/solutions/785903/qian-kge-gao-pin-dan-ci-by-leetcode-solu-3qk0/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。