题目描述

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

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

样例

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

算法1

(哈希表+红黑树) $O(logn)$

按照题意将存储每个数据cache的信息，包括key, value, 访问次数，访问时间；
哈希表记录key与cache信息的对应关系；
红黑树负责根据访问此处、访问时间对cache信息进行排序，用来决定超过capacity以后用来删除哪个cache。

cache信息的排序规则要自己重载写一下。

时间复杂度

set的底层位红黑树实现，故各种操作都是O(logn)

参考文献

C++ 代码

struct Node{
    int key, val, cnt, time;
    Node(int k, int v, int c, int t): key(k), val(v), cnt(c), time(t){}
};

struct cmp{
    bool operator()(const Node *a, const Node *b) const{
        if (a->cnt != b->cnt) return a->cnt < b->cnt;
        return a->time < b->time;
    }
};

class LFUCache {
private:
    int cap, timer, size;
    unordered_map<int, Node*> k2node;
    set<Node*, cmp> S;

public:
    LFUCache(int capacity) {
        cap = capacity;
        size = 0;
        timer = 0;
        k2node.clear();
        S.clear();
    }

    int get(int key) {
        ++timer;
        if (!k2node.count(key)) return -1;
        Node *visit = k2node[key];
        S.erase(visit);
        visit->time = timer;
        visit->cnt++;
        S.insert(visit);
        return visit->val;
    }

    void put(int key, int value) {
        if (cap == 0) return;
        ++timer;
        if (k2node.count(key)){
            Node *visit = k2node[key];
            S.erase(visit);
            visit->time = timer;
            visit->cnt++;
            visit->val = value;
            S.insert(visit);
        }
        else{
            if (size == cap){
                k2node.erase((*S.begin())->key); // S.begin()指向了一个*Node
                S.erase(S.begin());
                --size;
            }

            Node *new_Node = new Node(key, value, 1, timer);
            k2node[key] = new_Node;
            S.insert(new_Node);
            ++size;
        }
    }
};

/**
 * 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);
 */

算法2

(双哈希表) $O(1)$

这题真是复杂…
每个节点存储信息包括key, value, 访问频率；
第一个哈希表存储key与cache节点的映射关系；
第二个哈希表存储访问频率与相应双向链表的映射关系，通过频率可以访问所有该频率的cache，靠近双向链表的头部则说明访问时间越近；

get的时候，通过1号hash找到相应节点，其访问频率原为freq，把他从2号hash中freq对应链表上摘除，并加入freq + 1的链表；

put的时候：
1.如果key存在，基本跟get操作一致，只是多一步更新value的操作，
2.如果key不存在，首先检查是否超过capacity，如果超过了，要多一步操作，从频率最低的链表中摘除掉末尾的节点.
然后将新节点插入频率为1的链表中。

这个题面试应该不会考吧…

时间复杂度

哈希表查询为$O(1)$, 双向链表操作为$O(1)$, 故时间复杂度为$O(1)$。

参考文献

可以看看这个动画，还挺好理解的。
https://leetcode-cn.com/problems/lfu-cache/solution/lfuhuan-cun-by-leetcode-solution/

struct Node{
    int key, val, cnt;
    Node *prev, *post;
    Node(int k, int v, int c, Node *pre=0, Node *po=0): key(k), val(v), cnt(c), prev(pre), post(po){}
};

class LFUCache {
private:
    int cap, min_cnt;
    unordered_map<int, Node*> k2node;
    typedef pair<Node*, Node*> PNN; 
    unordered_map<int, PNN> f2ll; // 每个频率对应的双向链表首尾

    void remove(Node *node){
        node->prev->post = node->post;
        node->post->prev = node->prev;
    }

    void creat_linked_list(int freq){
        f2ll[freq] = {new Node(-2, -2, -2), new Node(-1, -1, -1)};
        f2ll[freq].first->post = f2ll[freq].second;
        f2ll[freq].second->prev = f2ll[freq].first;
    }

    void move_to_head(Node *node, Node *head){
        node->prev = head;
        node->post = head->post;
        node->post->prev = node;
        node->prev->post = node;
    }
public:
    LFUCache(int capacity) {
        cap = capacity;
        min_cnt = INT_MAX;
        k2node.clear();
        f2ll.clear();
    }

    int get(int key) {
        // cout << "key: " << key << endl;
        if (!k2node.count(key)) return -1;
        Node *visit = k2node[key]; // 找到节点
        // 将节点从链中删除
        remove(visit);
        // 顺便检查摘除后链表有没有空，如果空了，从哈希表中删除，并且更新min_cnt
        if (f2ll[visit->cnt].first->post == f2ll[visit->cnt].second){
            f2ll.erase(visit->cnt);
            if (min_cnt == visit->cnt) ++min_cnt;
        }
        // 找到freq + 1的链表，如果没有，创建一条
        if (!f2ll.count(visit->cnt + 1)){
            creat_linked_list(visit->cnt + 1);
        }
        PNN new_head_tail = f2ll[visit->cnt + 1];
        // 更新节点频率，并且插入相应链表头部
        visit->cnt++;
        move_to_head(visit, new_head_tail.first);
        return visit->val;
    }

    void put(int key, int value) {
        // cout << "key: " << key << "value: " << value << endl;
        if (cap == 0) return;
        if (k2node.count(key)){
            Node *visit = k2node[key]; // 找到节点
            // 将节点从链中删除
            remove(visit);
            // 顺便检查摘除后链表有没有空，如果空了，从哈希表中删除，并且更新min_cnt
            if (f2ll[visit->cnt].first->post == f2ll[visit->cnt].second){
                f2ll.erase(visit->cnt);
                if (min_cnt == visit->cnt) ++min_cnt;
            }

            // 找到freq + 1的链表，如果没有，创建一条
            if (!f2ll.count(visit->cnt + 1)){
                creat_linked_list(visit->cnt + 1);
            }
            PNN new_head_tail = f2ll[visit->cnt + 1];
            // 更新节点频率，并且插入相应链表头部
            visit->cnt++;
            move_to_head(visit, new_head_tail.first);
            // 更新节点的值
            visit->val = value;
        }
        else{
            if (k2node.size() == cap){
                PNN del_head_tail = f2ll[min_cnt];
                Node *de_node = del_head_tail.second->prev;
                remove(de_node);
                k2node.erase(de_node->key);
                delete de_node;
            }

            // 更新min_cnt, 并且创建新节点
            min_cnt = 1;
            Node *new_Node = new Node(key, value, 1);
            k2node[key] = new_Node;
            // 找到freq = 1的链表，如果没有，创建一条
            if (!f2ll.count(1)){
                creat_linked_list(1);
            }
            PNN new_head_tail = f2ll[1];
            // 插入链表头部
            move_to_head(new_Node, new_head_tail.first);
        }
    }
};

/**
 * 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);
 */