LFU缓存 shuitang

题目

460. LFU缓存

请你为 最不经常使用(LFU)缓存算法设计并实现数据结构。它应该支持以下操作:getput

  • get(key) - 如果键存在于缓存中,则获取键的值(总是正数),否则返回 -1。
  • put(key, value) - 如果键不存在,请设置或插入值。当缓存达到其容量时,则应该在插入新项之前,使最不经常使用的项无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最近 最少使用的键。

「项的使用次数」就是自插入该项以来对其调用 getput 函数的次数之和。使用次数会在对应项被移除后置为 0 。

进阶: 你是否可以在 O(1) 时间复杂度内执行两项操作?

解法

这题实属具有挑战性,没有想到O(1)的算法,在参考了题解之后,写(抄)了一下如下代码:

struct Node{
    int key, val,freq;
    Node(int _key, int _val, int _freq):
    key(_key), val(_val), freq(_freq){

    }
};

class LFUCache {
    int minFre;
    unordered_map<int,list<Node>> freq_list; //频率映射到链表
    unordered_map<int,list<Node>::iterator> key_node; //key值映射到链表节点指针(迭代器)
    int capacity;
public:
    LFUCache(int _capacity):capacity(_capacity) {
        minFre = 0;
        key_node.clear();
        freq_list.clear();
    }
    
    int get(int key) {
        if(capacity == 0) return -1;
        auto it = key_node.find(key);
        if(it == key_node.end()) return -1;
        list<Node>::iterator pNode = it->second;
        int val = pNode->val;
        int freq = pNode->freq;

        //更新操作
        freq_list[freq].erase(pNode);
        
        if(freq_list[freq].size() == 0){
            freq_list.erase(freq);
            if(minFre == freq) minFre++;
        }

        freq_list[freq+1].push_front(Node(key,val,freq+1));
        key_node[key] = freq_list[freq+1].begin();
        return val;
    }
    
    void put(int key, int value) {
        if(capacity == 0) return;
        auto it = key_node.find(key);
        if(it == key_node.end()){//要插入
            if( key_node.size() == capacity){
                auto it2 = freq_list[minFre].back();
                key_node.erase(it2.key);
                freq_list[minFre].pop_back();
                if(freq_list[minFre].size() == 0){
                    freq_list.erase(minFre);
                }
            }
            freq_list[1].push_front(Node(key,value,1));
            key_node[key] = freq_list[1].begin();
            minFre = 1;
        }else{ //要修改
            list<Node>::iterator pNode = it->second;
            //int val = pNode->val;
            int freq = pNode->freq;
            //更新操作
            freq_list[freq].erase(pNode);
            
            if(freq_list[freq].size() == 0){
                freq_list.erase(freq);
                if(minFre == freq) minFre++;
            }
            freq_list[freq+1].push_front(Node(key,value,freq+1));

            key_node[key] = freq_list[freq+1].begin();
        }
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

基本思想:

使用了关键的两个数据结构来保存信息:

  • fre -> LinkList 的哈希表,保存的是频率到 同一使用频率的节点构成的链表的映射,其中最近使用的节点保存在链表头;
  • key -> Node 的哈希表,保存的是 key 值到 节点的映射。

另外必要的信息:

  • Node: 节点保存 key, freq, value;

  • capacity: 容量

  • minFre: 当前最小的频率。当插入超出容量时,就需要来删除节点了,选择的正是最小频率对应的 LinkList 的来删除。

然后 get 和 put 操作需要维护上述的两个哈希表的信息,确保做到插入和查询都是 O(1) 的操作。