CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
题目
460. LFU缓存
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
get(key)- 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。put(key, value)- 如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 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) 的操作。