题目描述
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
- get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
- put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
Example1:
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
解题思路
-
其中 cnt 表示缓存使用的频率，time 表示缓存的使用时间，key 和 value 表示缓存的键值。
-
比较直观的想法就是我们用哈希表 key_table 以键 key 为索引存储缓存，建立一个平衡二叉树 S 来保持缓存根据 (cnt，time) 双关键字由于。在 C++ 中，我们可以使用 STL 提供的 std::set 类，set 背后的实现是红黑树：
-
对于 get(key) 操作，我们只要查看一下哈希表 key_table 是否有 key 这个键即可，有的话需要同时更新哈希表和集合中该缓存的使用频率以及使用时间，否则返回 -1。
-
对于 put(key, value) 操作，首先需要查看 key_table 中是否已有对应的键值。如果有的话操作基本等同于 get(key)，不同的是需要更新缓存的 value 值。如果没有的话相当于是新插入一个缓存，这时候需要先查看是否达到缓存容量 capacity，如果达到了的话，需要删除最近最少使用的缓存，即平衡二叉树中最左边的结点，同时删除 key_table 中对应的索引，最后向 key_table 和 S 插入新的缓存信息即可。
-
最近最少使用的缓存 -> 先按cnt进行排序，然后再按time进行排序
LRU （Least Recently Used）缓存机制（看时间） 「力扣」第 146 题：LRU缓存机制
在缓存满的时候，删除缓存里最久未使用的数据，然后再放入新元素；
数据的访问时间很重要，访问时间距离现在越近，就越不容易被删除；
就是喜新厌旧，淘汰在缓存里呆的时间最久的元素。在删除元素的时候，只看「时间」这一个维度。
LFU （Least Frequently Used）缓存机制（看访问次数）
在缓存满的时候，删除缓存里使用次数最少的元素，然后在缓存中放入新元素；
数据的访问次数很重要，访问次数越多，就越不容易被删除；
根据题意，「当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除」，即在「访问次数」相同的情况下，按照时间顺 序，先删除在缓存里时间最久的数据。
说明：本题其实就是在「力扣」第 146 题：LRU缓存机制 的基础上，在删除策略里多考虑了一个维度（「访问次数」）的信息。
struct Node {
int cnt, time, key, value;
Node(int _cnt, int _time, int _key, int _value):cnt(_cnt), time(_time), key(_key), value(_value){}
// 我们需要实现一个 Node 类的比较函数
// 将 cnt（使用频率）作为第一关键字，time（最近一次使用的时间）作为第二关键字
// 下面是 C++ 语言的一个比较函数的例子
bool operator < (const Node& rhs) const {
return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;
}
};
class LFUCache {
// 缓存容量，时间戳
int capacity, time;
unordered_map<int, Node> key_table;
set<Node> S; // 一段时间内 最少未使用
public:
LFUCache(int _capacity) {
capacity = _capacity;
time = 0;
key_table.clear();
S.clear();
}
int get(int key) {
if (capacity == 0) return -1;
auto it = key_table.find(key);
// 如果哈希表中没有键 key，返回 -1
if (it == key_table.end()) return -1;
// 从哈希表中得到旧的缓存
Node cache = it -> second;
// 从平衡二叉树中删除旧的缓存
S.erase(cache);
// 将旧缓存更新
cache.cnt += 1;
cache.time = ++time;
// 将新缓存重新放入哈希表和平衡二叉树中
S.insert(cache);
it -> second = cache;
return cache.value;
}
void put(int key, int value) {
if (capacity == 0) return;
auto it = key_table.find(key);
if (it == key_table.end()) {
// 如果到达缓存容量上限
if (key_table.size() == capacity) {
// 从哈希表和平衡二叉树中删除最近最少使用的缓存
key_table.erase(S.begin() -> key);
S.erase(S.begin());
}
// 创建新的缓存
Node cache = Node(1, ++time, key, value);
// 将新缓存放入哈希表和平衡二叉树中
key_table.insert(make_pair(key, cache));
S.insert(cache);
}
else {
// 这里和 get() 函数类似
Node cache = it -> second;
S.erase(cache);
cache.cnt += 1;
cache.time = ++time;
cache.value = value;
S.insert(cache);
it -> second = cache;
}
}
};
