来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/lfu-cache

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

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

进阶：

你是否可以在 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

二、题目解析

LFU算法是LRU算法的改进版本，LRU算法强调最近最少使用，逐步淘汰掉很久没有使用的缓存。而LFU在LRU的基础上引入了使用频率限制，优先使用频率来淘汰缓存。在频率同等的情况下，再通过LRU淘汰较久没有使用的。

虽然只是增加了一个维度的判断，但是在逻辑和编码上，多出来的就麻烦了不止一个档次。因为题目要求在O(1)的时间复杂度内完成两项操作。对于get操作而言，如果使用哈希表来保存所有的缓存节点，可以在O(1)的时间复杂度完成。但是对于put操作来说，想要把它在O(1)的时间复杂度内插入，就不简单了，必须要有合适的数据结构来支撑才行，因为除了保存频次以外还有记录节点的使用时间。如果像LRU一样使用链表来存，每个缓存节点都要先找到合适的位置才能插入，时间复杂度是O(n)。

这里可以采取的方式是使用两个哈希表来保存所有的节点，其中一个以缓存的key值作为哈希表的key，另外一个以缓存出现的频率作为哈希表的key。假设保存所有缓存节点的哈希表为cache，保存频率的哈希表为freq，那么它的操作逻辑为：

三、代码

// 缓存节点
struct cacheNode {
    int key, val, freq; // 键
};

class LFUCache {
private:
    unordered_map<int, list<cacheNode *>> freq; // 保存所有频次的节点
    unordered_map<int, cacheNode *> cache; // 保存所有的缓存节点
    int min; // 出现最小的频次
    int capacity; // 容量
    int size; // 大小

    void incrFreq(unordered_map<int, cacheNode *>::iterator &itCache) {
        cacheNode *node;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        node = itCache->second;

        // 找到对应频率的链表
        itFreq = freq.find(node->freq);
        if (itFreq == freq.end())
            throw logic_error("unexpect error: cannot file list in freq map");

        // 从当前链表移除
        itFreq->second.remove(node);
        if (itFreq->second.empty()) {
            freq.erase(node->freq);
            // 当前删除的节点是最小频率节点
            if (node->freq == min)
                min++;
        }

        // 增加频率
        node->freq++;
        itFreq = freq.find(node->freq);
        if (itFreq == freq.end()) {
            freq.insert(pair<int, list<cacheNode *>>(node->freq, list<cacheNode *>()));
            itFreq = freq.find(node->freq);
        }

        itFreq->second.push_front(node);
    }

    // 添加新节点
    void putNewNode(int key, int value) {
        cacheNode *node, *p;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (this->size == this->capacity) {
            // 缓存容量上限了，到使用频率最低的删除最近最少使用
            itFreq = freq.find(min);
            if(itFreq == freq.end()) // 这里必须要有节点，否则异常
                throw logic_error("unexpect error: cannot find list in min freq map");

            if (itFreq->second.empty()) // 链表的节点数量不为0
                throw logic_error("unexpect error: min freq list is empty");

            node = itFreq->second.back();
            // 弹出最近最少使用的，先清除缓存列表中的
            cache.erase(node->key);
            // 然后清除频率表中的
            itFreq->second.pop_back();
            if (itFreq->second.empty()) {
                // 如果列表中的元素删完了，完全移除key
                freq.erase(min);
            }
            this->size--;
        } else {
            node = new cacheNode;
        }
        // 给node节点赋值
        min = node->freq = 1;
        node->key = key;
        node->val = value;
        // 先插入到以频率为key的哈希表
        itFreq = freq.find(min);
        if(itFreq == freq.end()) { // 这里可能是不存在对应节点的，如果不存在，创建一个节点
            freq.insert(pair<int, list<cacheNode *>>(min, list<cacheNode *>()));
            itFreq = freq.find(min);
        }
        itFreq->second.push_front(node);
        // 然后插入到缓存哈希表
        cache.insert(pair<int, cacheNode*>(key, node));
        this->size++;
    }

    // 插入已经存在的节点
    void putExistNode(int key, int value, unordered_map<int, cacheNode *>::iterator &itCache) {
        cacheNode *node;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        // 找到了对应的缓存，更新缓存的value，然后把频率加一
        node = itCache->second;
        node->val = value;

        incrFreq(itCache);
    }
public:
    LFUCache(int capacity) {
        this->size = 0;
        this->min = 0;
        this->capacity = capacity;
    }

    int get(int key) {
        cacheNode *node;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (capacity == 0)
            return -1;

        itCache = cache.find(key);
        if (itCache == cache.end()) // 没有找到对应的cache，直接返回
            return -1;

        incrFreq(itCache);
        return itCache->second->val;
    }

    void put(int key, int value) {
        cacheNode *node;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (capacity == 0)
            return;

        itCache = cache.find(key);
        if (itCache == cache.end()) {
            // 插入新值
            putNewNode(key, value);
        } else {
            // 更新旧值
            putExistNode(key, value, itCache);
        }
    }
};