【每日打卡】 [leetcode]460-LFU 缓存

来源：力扣（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

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);
        }
    }
};

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

// 缓存节点

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

}

};

2026 年 1 月
一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

一、题目描述

二、题目解析

三、代码

发表评论 取消回复

发表评论取消回复