leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0692.cpp (1303B)

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