出现次数的TopK问题
出现次数的TopK问题
http://www.nowcoder.com/questionTerminal/fd711bdfa0e840b381d7e1b82183b3ee
#include <unordered_map> class Solution { public: /** * return topK string * @param strings string字符串vector strings * @param k int整型 the k * @return string字符串vector<vector<>> */ vector<vector<string> > topKstrings(vector<string>& strings, int k) { // write code here vector<vector<string> > ans; if (strings.size() == 0 || strings.size() < k) return ans; // 记录每个元素出现的次数 unordered_map<string, int> hash; for (const auto& string : strings) { hash[string]++; } // 建立小根堆,按照出现次数排序,次数相同按照字典序 auto cmp = [](const pair<string, int>& p1, const pair<string, int> p2) { if (p1.second != p2.second) return p1.second > p2.second; return p1.first < p2.first; }; // 将全部元素入堆 priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> max_heap(cmp); auto p_iter = hash.begin(); for ( ; p_iter != hash.end(); p_iter++) { max_heap.emplace(*p_iter); if (max_heap.size() > k) max_heap.pop(); } while (!max_heap.empty()) { pair<string, int> p = min_heap.top(); max_heap.pop(); ans.insert(ans.begin(), vector<string>{p.first, to_string(p.second)} ); } return ans; } };