题解 | #LFU缓存结构设计#

class Solution {
private:
    typedef list<vector<int> > vecList; //定义元素为向量的双向链表，向量里为[频次，键，值]
    unordered_map<int, vecList> freq_map; //建立频次到双向链表的哈希表
    unordered_map<int, vecList::iterator> key_map;
    //建立键到双向链表迭代器的哈希表（迭代器可以简单理解为在双向链表中的指针类，通过它可以得到里面的元素）
    int least = 0; //记录当前最小频次
    int K;
    void refresh_key(vecList::iterator vlist, int key, int value) { //更新和加入新key都会刷新
        int num = (*vlist)[0]; //这里迭代器解引用（类似指针）取下标得到频次
        freq_map[num].erase(vlist); //在该频次下的双向链表中擦除迭代器指向位置中的元素
        if(freq_map[num].empty()) { //如果双向链表被擦空了
            freq_map.erase(num); //删除该频次的映射
            if(least == num) least++; //如果当前频次为最小频次，最小频次加一
        }
        freq_map[num + 1].push_front({num + 1, key, value});
        //插入频次加一的双向链表表头（若无此映射会自动创建空双向链表）
        key_map[key] = freq_map[num + 1].begin(); //更新键到双向链表迭代器的映射
    }
    void set(int key, int value) {
        auto it = key_map.find(key);
        if(it != key_map.end())
            refresh_key(it->second, key, value);
        else {
            if(K == 0) {
                int old_key = freq_map[least].back()[1];
                freq_map[least].pop_back();
                if(freq_map[least].empty())
                    freq_map.erase(least);
                key_map.erase(old_key);
            }
            else
                K--;
            least = 1;
            freq_map[1].push_front({1, key, value});
            key_map[key] = freq_map[1].begin();
        }
    }
    int get(int key) {
        auto it = key_map.find(key);
        if(it != key_map.end()) {
            auto vList_it = it->second;
            int value = (*vList_it)[2];
            refresh_key(vList_it, key, value);
            return value;
        }
        else
            return -1;
    }
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        K = k;
        vector<int> res;
        for(auto vec:operators) {
            if(vec[0] == 1)
                set(vec[1], vec[2]);
            else
                res.push_back(get(vec[1]));
        }
        return res;
    }
};