leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0692.cpp (1303B)

0 // sort: O(nlogn) 1 class Solution { 2 public: 3 vector<string> topKFrequent(const vector<string> &words, int k) { 4 unordered_map<string, int> um; 5 for (const auto &w : words) 6 um[w]++; 7 8 vector<pair<int, string>> vec(um.size()); 9 vector<string> res(k); 10 11 int count = 0; 12 for (const auto &[k, v] : um) 13 vec[count++] = {-v, k}; 14 sort(vec.begin(), vec.end()); 15 for (int i = 0; i < k; i++) 16 res[i] = vec[i].second; 17 18 return res; 19 } 20 }; 21 22 // heap: O(nlogk) 23 class Solution { 24 typedef pair<string, int> psi; 25 static constexpr const auto cmp = [](const psi &p1, const psi &p2) { 26 if (p1.second == p2.second) return p1.first < p2.first; 27 return p1.second > p2.second; 28 }; 29 30 public: 31 vector<string> topKFrequent(const vector<string> &words, int k) { 32 unordered_map<string, int> um; 33 for (const auto &w : words) 34 um[w]++; 35 36 priority_queue<psi, vector<psi>, decltype(cmp)> pq(cmp); 37 vector<string> res(k); 38 39 for (auto it : um) { 40 pq.push(it); 41 if (pq.size() > k) pq.pop(); 42 } 43 44 int count = k - 1; 45 while (!pq.empty()) 46 res[count--] = pq.top().first, pq.pop(); 47 48 return res; 49 } 50 };