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