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

解题思路：使用双哈希表 set + map

使用map存储key和其所有的信息node，包括key值、频率、值、最近使用时间点

使用set从小到大存储node,node根据频率和时间点进行排序，频率不相等则根据频率大小进行排序，频率相等则根据时间大小进行排序，时间大的说明使用时间更近。

#include <climits>
#include <deque>
#include <unordered_map>
#include <vector>
struct Node{
    int keys,vals,fres,times;
    Node(int a,int b,int c,int d):keys(a),vals(b),fres(c),times(d){}
    //重载<运算符，以便根据频率和使用时间点，从小到大存于set中
    bool operator<(const Node & rhs) const
    {
        //如果频率相等，则返回时间小的，否则返回频率小的
        return fres == rhs.fres? times < rhs.times : fres < rhs.fres;
    }

};
class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    int get(int key)
    {
        //排除异常
        if(maxsize == 0)
            return -1;
        auto iter = m.find(key);
        //如果没有这个key值，则返回-1
        if(iter == m.end())
            return -1;
        //取出当前键值
        Node temp = iter->second;
        s.erase(temp);//在set中删除
        temp.fres += 1;//频率+1
        temp.times = ++time;//更新使用的时间点
        iter->second = temp;//存回更新后的值
        s.insert(temp);//存回更新后的值
        return temp.vals;
    }
    void put(int key,int value)
    {
        //排除异常
        if(maxsize == 0)
            return;
        auto iter = m.find(key);
        //如果没有该键值
        if(iter == m.end())
        {
            //如果等于最大长度，则要删除set的第一个元素，这个元素是符合题意的
            if(m.size() == maxsize)
            {
                m.erase(s.begin()->keys);
                s.erase(s.begin());
            }
            //存入新的结点，频率初始为1，时间为当前时间点
            Node temp = Node(key,value,1,++time);
            m.insert({key, temp});
            s.insert(temp);
        }
        //如果有该键值，则更新该键值,类似get
        else 
        {
            //取出当前键值
            Node temp = iter->second;
            s.erase(temp);//在set中删除
            temp.fres += 1;//频率+1
            temp.times = ++time;//更新使用的时间点
            temp.vals = value;//更新value
            iter->second = temp;//存回更新后的值
            s.insert(temp);//存回更新后的值
        }
    }


    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        maxsize = k;
        time = 0;
        for(auto x: operators)
        {
            if(x[0] == 1)
                put(x[1],x[2]);
            else
                res.push_back(get(x[1]));
        }
        return res;
    }

private:
    int maxsize,time;
    unordered_map<int, Node> m;
    set<Node> s;
};