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; }; vectorstring topKFrequent(vectorstring words, int k) { unordered_mapstring, int table; for (auto w : words) { table[w]; } priority_queueNode, vectorNode 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); }*/ } vectorstring 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; }; vectorstring topKFrequent(vectorstring words, int k) { unordered_mapstring, int table; for (auto w : words) { table[w]; } priority_queueNode, vectorNode 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); }*/ } vectorstring 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; }; vectorstring topKFrequent(vectorstring words, int k) { unordered_mapstring, int table; for (auto w : words) { table[w]; } priority_queueNode 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); } } vectorstring 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: vectorstring topKFrequent(vectorstring words, int k) { unordered_mapstring, int cnt; for (auto word : words) { cnt[word]; } auto cmp [](const pairstring, int a, const pairstring, int b) { return a.second b.second ? a.first b.first : a.second b.second; }; priority_queuepairstring, int, vectorpairstring, int, decltype(cmp) que(cmp); for (auto it : cnt) { que.emplace(it); if (que.size() k) { que.pop(); } } vectorstring 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 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。