LRU题目姊妹篇，个人认为这道题难度比LRU大，主要需要记录访问次数，如果访问次数一致再按照LRU访问时间。解题思路参考了力扣官方文章
C++里可以使用set（底层红黑树），排序依据是访问次数和访问时间，因此需要重载比较运算符。
方法一AC代码:
struct Node {
int m_cnt, m_time, m_key, m_value;
Node(int cnt, int time, int key, int value):m_cnt(cnt), m_time(time), m_key(key), m_value(value){}
bool operator < (const Node& rhs) const {
return m_cnt == rhs.m_cnt ? m_time < rhs.m_time : m_cnt < rhs.m_cnt;
}
};
class LFUCache {
private:
int m_capacity, m_time;
unordered_map<int, Node> m_cache;
set<Node> m_set;
public:
LFUCache(int capacity):m_capacity(capacity),m_time(0) {}
int get(int key) {
auto it = m_cache.find(key);
if(it == m_cache.end())
return -1;
Node node = it->second;
m_set.erase(node);
node.m_cnt++;
node.m_time = ++m_time;
m_set.insert(node);
it->second = node;
return node.m_value;
}
void put(int key, int value) {
if(m_capacity == 0) return;
auto it = m_cache.find(key);
if(it == m_cache.end())
{
if(m_cache.size() == m_capacity)
{
m_cache.erase(m_set.begin()->m_key);
m_set.erase(m_set.begin());
}
Node node = Node(1,++m_time,key,value);
m_set.insert(node);
m_cache.insert(make_pair(key,node));
}
else
{
Node node = it->second;
m_set.erase(node);
node.m_time = m_time++;
node.m_cnt++;
node.m_value = value;
m_set.insert(node);
it->second = node;
}
}
};
/**
* 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);
*/实现的时候遇到问题，调试的代码（代码中存在bug)
#include <iostream>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;
struct Node {
int m_cnt, m_time, m_key, m_value;
Node(int cnt, int time, int key, int value):m_cnt(cnt), m_time(time), m_key(key), m_value(value){}
bool operator < (const Node& rhs) const {
return m_cnt == rhs.m_cnt ? m_time < rhs.m_time : m_cnt < rhs.m_cnt;
}
};
class LFUCache {
private:
int m_capacity, m_time;
unordered_map<int, Node> m_cache;
set<Node> m_set;
public:
LFUCache(int capacity):m_capacity(capacity),m_time(0) {
m_cache.clear();
m_set.clear();
}
int get(int key) {
auto it = m_cache.find(key);
if(it == m_cache.end())
return -1;
Node node = it->second;
m_set.erase(node);
node.m_cnt++;
node.m_time++;
m_set.insert(node);
it->second = node;
return node.m_value;
}
void put(int key, int value) {
if(m_capacity == 0) return;
auto it = m_cache.find(key);
if(it == m_cache.end())
{
if(m_cache.size() == m_capacity)
{
m_cache.erase(m_set.begin()->m_key);
m_set.erase(m_set.begin());
}
Node node = Node(1,++m_time,key,value);
m_set.insert(node);
m_cache.insert(make_pair(key,node));
}
else
{
Node node = it->second;
m_set.erase(it->second);
node.m_time++;
node.m_cnt++;
node.m_value = value;
m_set.insert(node);
it->second = node;
}
}
};
int main()
{
LFUCache cache(2);
cache.put(2,1);
cache.put(3,2);
cache.get(3);
cache.get(2);
cache.put(4,3);
int ans = cache.get(2);
cout << ans << endl;
cache.get(3);
cache.get(4);
return 0;
}
方法二：双哈希表
双哈希表比较巧妙，一个哈希表维护key和迭代器，另一个哈希表维护相同频率的链表。
struct Node {
int key, val, freq;
Node(int _key,int _val,int _freq): key(_key), val(_val), freq(_freq){}
};
class LFUCache {
private:
int minfreq, capacity;
unordered_map<int, list<Node>::iterator> key_table;
unordered_map<int, list<Node>> freq_table;
public:
LFUCache(int _capacity) :minfreq(0),capacity(_capacity){
key_table.clear();
freq_table.clear();
}
int get(int key) {
if(capacity == 0) return -1;
unordered_map<int, list<Node>::iterator>::iterator it = key_table.find(key);
if(it == key_table.end()) return -1;
list<Node>::iterator node = it->second;
int val = node->val,freq = node->freq;
freq_table[freq].erase(node);
//如果链表为空，需要删除key_table
if(freq_table[freq].size() == 0){
freq_table.erase(freq);
if(minfreq == freq) minfreq += 1;
}
freq_table[freq + 1].push_front(Node(key,val,freq + 1));
key_table[key] = freq_table[freq + 1].begin();
return val;
}
void put(int key, int value) {
if(capacity == 0) return;
unordered_map<int, list<Node>::iterator>::iterator it = key_table.find(key);
if(it == key_table.end()){
if(key_table.size() == capacity){
Node node = freq_table[minfreq].back();
key_table.erase(node.key);
freq_table[minfreq].pop_back();
if(freq_table[minfreq].size() == 0)
freq_table.erase(minfreq);
}
freq_table[1].push_front(Node(key,value,1));
key_table[key] = freq_table[1].begin();
minfreq = 1;
}else{
list<Node>::iterator node = it->second;
int freq = node->freq;
freq_table[freq].erase(node);
if(freq_table[freq].size() == 0){
freq_table.erase(freq);
if(minfreq == freq) minfreq += 1;
}
freq_table[freq + 1].push_front(Node(key,value,freq + 1));
//key_table.insert(make_pair(key, freq_table[freq + 1].begin()));
key_table[key] = freq_table[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);
*/上面有一行注释代码，如果使用insert这里会报错，原因是已经有key键，插入失败，而我们又删除了对应freq_table中的元素，因而访问迭代器失效，通过Address Sanitizer 检测会报错如下:
=================================================================
==30==ERROR: AddressSanitizer: heap-use-after-free on address 0x6030000002f4 at pc 0x00000034e9a1 bp 0x7fffb0e87070 sp 0x7fffb0e87068运行效率惊人100%
Runtime: 92 ms, faster than 100.00% of C++ online submissions for LFU Cache.
Memory Usage: 42.3 MB, less than 79.62% of C++ online submissions for LFU Cache.
Next challenges: