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

#include <algorithm>
#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    unordered_map<int, int> hashValue;
    unordered_map<int, int> hashOrder;// 用于保存顺序
    unordered_map<int, clock_t> hashTime;// 用于使用时间
    int cap;
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        cap = k;
        int Asize = operators.size();
        if(Asize==0){
            return res;
        }

        for(int i = 0; i<Asize; i++){
            // 开始导出内容
            if(operators[i][0] == 1){
                // set
                set(operators[i][1], operators[i][2]);
            }
            else if(operators[i][0] == 2)
            {
                // get
                int resNum = get(operators[i][1]);
                res.push_back(resNum);
            }
            
        }
        return res;
    }

    void set(int key, int value){
        if(hashValue.find(key)!=hashValue.end()){
            // 找到了
            hashValue[key] = value;
            hashOrder[key] += 1;
            hashTime[key] += 1;
        }
        else{
            // 先检查删除
            if(hashValue.size()>=cap){
                // 删除
                int del_key = hashOrder.begin()->first;
                int minValue = hashOrder.begin()->second; // 先设置最小值
                for(auto i : hashOrder){
                    if(i.second<minValue){
                        del_key = i.first;
                        minValue = i.second;
                    }
                    else if(i.second==minValue){
                        //取时间短的
                        if(hashTime[i.first]<hashTime[del_key]){
                            del_key = i.first;
                            minValue = i.second;
                        }
                    }
                }
                
                hashValue.erase(del_key);
                hashOrder.erase(del_key);
                hashTime.erase(del_key);
            }
            hashValue[key] = value;
            hashOrder[key] = 1;
            hashTime[key] = clock();
        }
    }

    int get(int key){
        if(hashValue.find(key)!=hashValue.end()){
            // 找到了
            hashOrder[key] += 1;
            hashTime[key] = clock();
            return hashValue[key];
        }
        else{
            return -1;
        }
    }
};