剑指 Offer II 059. 数据流的第 K 大数值

  1. class KthLargest {
  2. public:
  3.     priority_queue<int, vector<int>, greater<int>> q;//小顶堆，只维护k个最大的元素
  4.     //则堆顶就是第k大的元素
  5.     int k;
  6.     KthLargest(int k, vector<int>& nums) {
  7.         this->k = k;
  8.         for (auto& x: nums) {
  9.             add(x);
  10.         }
  11.     }
  13.     int add(int val) {
  14.         q.push(val);
  15.         if (q.size() > k) {
  16.             q.pop();
  17.         }
  18.         return q.top();
  19.     }
  20. };

剑指 Offer II 060. 出现频率最高的 k 个数字

上一题的升级版本，注意这里的cmp使用仿函数的方法

  1. class Solution {
  2.     struct cmp {
  3.         bool operator()(pair<int,int> a, pair<int, int> b){
  4.             return a.second > b.second;
  5.         }
  6.     };
  7.     unordered_map<int, int> hash;
  8.     priority_queue<pair<int, int>, vector<pair<int,int>> , cmp> q;
  9. public:
  10.     vector<int> topKFrequent(vector<int>& nums, int k) {
  11.         for(auto num : nums) {
  12.             hash[num]++;
  13.         }
  14.         for(auto [key, value] : hash) {
  15.             q.emplace(key, value);
  16.             if(q.size() > k) {
  17.                 q.pop();
  18.             }
  19.         }
  20.         vector<int> ret;
  21.         while(!q.empty()) {
  22.             ret.push_back(q.top().first);
  23.             q.pop();
  24.         }
  25.         return ret;
  26.     }
  27. };