题解 | 设计LFU缓存结构

class Solution {
  public:
    vector<int> LFU(vector<vector<int> >& ops, int k) {
        struct LFUCache {
            int cap = 0, sz = 0, minf = 0;
            unordered_map<int, int> val;                        // key -> value
            unordered_map<int, int> freq;                       // key -> freq
            unordered_map<int, list<int>::iterator>pos;        
            unordered_map<int, list<int>>bucket;               
            LFUCache(int c) : cap(c) {}
            int get(int key) {
                if (!val.count(key)) return -1;
                int f = freq[key];
                // 从旧频次链表移除
                bucket[f].erase(pos[key]);
                if (bucket[f].empty()) {
                    bucket.erase(f);
                    if (minf == f) ++minf;
                }
                // 插入到新频次链表末尾
                ++freq[key];
                int nf = freq[key];
                bucket[nf].push_back(key);
                pos[key] = --bucket[nf].end();
                return val[key];
            }
            void set(int key, int value) {
                if (cap == 0) return;
                if (val.count(key)) {           // 已存在：更新并提频
                    val[key] = value;
                    (void)get(key);
                    return;
                }
                if (sz == cap) {                // 淘汰 minf 链表最旧的
                    int victim = bucket[minf].front();
                    bucket[minf].pop_front();
                    if (bucket[minf].empty()) bucket.erase(minf);
                    pos.erase(victim);
                    freq.erase(victim);
                    val.erase(victim);
                    --sz;
                }
                // 插入新 key
                val[key] = value;
                freq[key] = 1;
                bucket[1].push_back(key);
                pos[key] = --bucket[1].end();
                minf = 1;
                ++sz;
            }
        };
        LFUCache cache(k);
        vector<int> res;
        for (auto& op : ops) {
            if (op[0] == 1) {            // set(x, y)
                cache.set(op[1], op[2]);
            } else if (op[0] == 2) {     // get(x)
                res.push_back(cache.get(op[1]));
            }
        }
        return res;
    }
};