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

class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */

    struct Node {
        int key;
        int val;
        int fre;
        Node() {};
        Node(int a,int b,int c):key(a),val(b),fre(c){}
    };


    unordered_map<int, list<Node>> fre;  // 里面是频率的和对应频率的key值
    unordered_map<int,list<Node>::iterator > site;  // key对应的位置
    int min_fre = -1; // 对应最小频率
    int len;

    void set(int key, int value) {
        if(fre.empty()) {
            min_fre=1;
            fre[1].push_back(Node(key,value,1));
            site[key]=--fre[1].end();
        } else {
            // 有数字
            if(site.count(key)!=0) {
                // 原来就有

                auto iter = site[key];
                auto node = *iter;
                // 先删除原来的
                fre[node.fre].erase(iter);
                if(fre[node.fre].empty()) {
                    fre.erase(node.fre);
                    if(node.fre==1) {
                        min_fre=node.fre+1;
                    }
                }
                node.fre++;
                node.val=value;
                // 这边频率要往上移动
                fre[node.fre].push_back(node);
                site[node.key]=--fre[node.fre].end();
            } else {
                if(site.size()<len) {
                    // 直接插入
                    fre[1].push_back(Node(key,value,1));
                    min_fre=1;
                    site[key]=--fre[1].end();
                } else {
                    // 删除一个
                    auto node =  *fre[min_fre].begin();
                    fre[node.fre].pop_front();
                    site.erase(node.key);
                    if(fre[node.fre].empty()) {
                        fre.erase(node.fre);
                    }
                    // 开始插入
                    fre[1].push_back(Node(key,value,1));
                    min_fre=1;
                    site[key]=--fre[1].end();
                }
            }
        }
    }


    int get(int key) {
        if(site.count(key)==0){
            return -1;
        }
        int res = site[key]->val;
        // 开始换位置
        auto node = *site[key];
        fre[node.fre].erase(site[key]);
        if(fre[node.fre].empty()) {
            fre.erase(node.fre);
            if(node.fre==1) {
                min_fre=node.fre+1;
            }
        }
        node.fre++;
        fre[node.fre].push_back(node);
        site[node.key]=--fre[node.fre].end();
        return res;
    }



    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        len=k;
        for(auto op : operators) {
            if(op.size()==3) {
                set(op[1],op[2]);
            } else {
                res.push_back(get(op[1]));
            }
        }
        return res;
    }
};