双hash + 双链表

  • hash: <key, list<node>:: iterator></node>

  • cnt: <freq, list<node> >
    使用list来模拟双链表</node>

    #include<unordered_map>
typedef struct node{
  int key, value, freq;
}node;
class Solution {
public:
  int minFreq, hashSize;
  unordered_map<int, list<node>::iterator> hash;
  unordered_map<int, list<node> > cnt;

  void set(int x, int y){
      if(hash.find(x) == hash.end()){
          if(hash.size() == hashSize){
              auto t = cnt[minFreq].back();
              hash.erase(t.key);
              cnt[minFreq].pop_back();
              if(cnt[minFreq].size() == 0){
                  cnt.erase(minFreq);
              }
          }
          cnt[1].push_front({x, y, 1});
          hash[x] = cnt[1].begin();
          minFreq = 1;
      }
      else{
          auto t = hash[x];
          int freq = t->freq;
          cnt[freq].erase(t);
          if(cnt[freq].size() == 0){
              cnt.erase(freq);
              if(minFreq == freq) minFreq ++;
          }
          cnt[freq + 1].push_front({x, y, freq + 1});
          hash[x] = cnt[freq + 1].begin();
      }
  }

  int get(int x){
      if(hash.find(x) == hash.end()) return -1;
      auto t = hash[x];
      int freq = t->freq;
      int y = t->value;
      cnt[freq].erase(t);
      if(cnt[freq].size() == 0){
          cnt.erase(freq);
          if(minFreq == freq) minFreq++;
      }
      cnt[freq + 1].push_front({x, y, freq + 1});
      hash[x] = cnt[freq + 1].begin();
      return y;
  }

  vector<int> LFU(vector<vector<int> >& operators, int k) {
      // write code here
      vector<int> ans;
      if(k <= 0) return ans;
      minFreq = 0, hashSize = k;
      for(int i = 0; i < operators.size(); i++){
          auto t = operators[i];
          if(t[0] == 1){
              set(t[1], t[2]);
          }
          else{
              ans.push_back(get(t[1]));
          }
      }
      return ans;
  }
};