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

LFU缓存结构设计
题意:
设计一个缓存结构实现两个功能:
set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
并且缓存中最多放k条记录,如果添加第k+1条时，将在缓存的k个记录中删除一个被set和get调用次数最少的如果有多个调用次数相同则删除最早加入的.

输出描述:
输出每次执行get操作所获取的value值，如果不存在则用-1代替

案例:
输入：[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3
返回值：[4,-1]
说明：在执行"1 4 4"后，"1 1 1"被删除。因此第二次询问的答案为-1

方法一 map+链表

考虑set操作,需要达到 $O(1)$ 复杂度。首先可以将访问的频次当作一条数据的标识，使用unordered_map,这样访问在需要删除一条数据的情况下获取访问频次最少的复杂度只需要 $O(1)$ ,之后考虑存储方式因为同频次的条数不止一条,如果按频次集合存储（即：map<int,vector<int>>）则如果删除中间的某一条则复杂度会达到 $O(n)$ ，所以考虑使用链表,使用stl中list总体复杂度为 $O(1)$ ，这样set的操作的复杂度就可以达到 $O(1)$ ,对于最小频次的获取可以定义一个mins来维护.
get操作只要使用unordered_map存储获取值即可到达 $O(1)$ 复杂度
图片说明 </int>

  unordered_map<int, list<vector<int> > > now;    //存储原数对应位置
    unordered_map<int, list<vector<int> > ::iterator> pre; //对应结点的迭代器
    int ks = 0, mins = 0; //ks为内存大小 mins为最低的频次
    void update(list<vector<int> >::iterator it, int x, int y){ // 更新结点
        int sum = (*it)[0];
        now[sum].erase(it); 
        if(now[sum].size() == 0) //如果当前没有元素且下标正好是mins则更新
            if(sum == mins) mins ++;
        now[sum + 1].push_front({sum + 1, x, y}); // 更新访问次数
        pre[x] = now[sum + 1].begin();
    }
    void set(int x, int y){
        auto ns = pre.find(x);
        if(ns != pre.end()){ // 如果之前已经设置过值则更新访问次数
            update(ns->second, x, y);
        }else{
            if(ks){ //如果还有多余的内存则直接插入
                ks --;
                mins = 1;
                now[mins].push_front({1, x, y});
                pre[x] = now[mins].begin();
            }else{ //如果没有多余的内存则吧当前访问次数最少且最早加入的点删除
                int tt = now[mins].back()[1]; //获取访问次数最少且最早加入
                pre.erase(tt); //清空pre中的tt节点
                now[mins].pop_back(); 
                mins = 1;
                now[mins].push_front({1, x, y}); //插入新节点
                pre[x] = now[mins].begin();
            }
        }
    }
    int get(int x){ //查找x点的val值
        auto tt = pre.find(x);
        if(tt == pre.end()) return -1;
        update(tt->second, (*tt->second)[1], (*tt->second)[2]); //查找后也要更新节点访问
        return (*tt->second)[2];
    }
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        ks = k;
        vector<int> ans;
        for(int i = 0; i < operators.size(); i ++){
            if(operators[i][0] == 1){
                set(operators[i][1], operators[i][2]);
            }else{
                int ss = get(operators[i][1]);
                ans.push_back(ss);
            }
        }
        return ans;
    }

时间复杂度: $O(n)$ get和set的操作只需要 $O(1)$ 所以最多会遍历一遍操作数
空间复杂度: $O(n)$ map存储内容

方法二 map + vector

思路与上述相同只是set操作中链表换成了vector这样set操作的复杂度将会达到 $O(n)$

unordered_map<int, vector<int>> now; 
    unordered_map<int, pair<int,int>> pp;
    int mins = 1; //访问的最小频次
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here、、
        vector<int> ans;
        for(int i = 0; i < operators.size(); i ++){
            if(operators[i][0] == 1){ //第一个操作
                if(pp.find(operators[i][1]) == pp.end()){ //如果之前没有存储过该元素
                    if(!k){ //判断内存是否还有剩 如果有直接添加 没有则删除访问次数最少且最早加入的点
                        pp.erase(now[mins][0]);
                        now[mins].erase(now[mins].begin());
                    }else k --;
                    mins = 1;
                    now[mins].push_back(operators[i][1]);
                    pp[operators[i][1]] = {operators[i][2], mins};
                }else{ // 之前有存储过该元素 则更新频次和更新值
                    int tt = pp[operators[i][1]].second;
                    now[tt].erase(find(now[tt].begin(), now[tt].end(), operators[i][1]));
                    now[tt + 1].push_back(operators[i][1]); 
                    pp[operators[i][1]] = {operators[i][2], tt + 1};//更新该元素的频次和值
                }
            }else{ //第二个操作
                auto ss = pp.find(operators[i][1]);
                if(ss == pp.end()) ans.push_back(-1); 
                else{
                    //更新频次
                    int tt = pp[operators[i][1]].second;
                    now[tt].erase(find(now[tt].begin(), now[tt].end(), operators[i][1]));
                    now[tt + 1].push_back(operators[i][1]);
                    pp[operators[i][1]] = {pp[operators[i][1]].first, tt + 1};
                    ans.push_back(pp[operators[i][1]].first);
                }
            }
        }
        return ans;
    }

时间复杂度: $O(n^2)$ 删除最早的记录需要 $O(n)$ 的复杂度所以最坏会达到 $O(n^2)$
空间复杂度: $O(n)$ map存储内容