题目形容
这是 LeetCode 上的 「460. LFU 缓存」，难度为 「艰难」。
Tag :「链表」、「双向链表」、「设计」
请你为 「最不常常应用（LFU）」 缓存算法设计并实现数据结构。
实现 LFUCache 类：
LFUCache(int capacity)– 用数据结构的容量capacity初始化对象int get(int key)– 如果键存在于缓存中，则获取键的值，否则返回 -1。void put(int key, int value)– 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不常常应用的项有效。在此问题中，当存在平局（即两个或更多个键具备雷同应用频率）时，应该去除 「最近最久未应用」 的键。
留神「项的应用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。应用次数会在对应项被移除后置为 0。
为了确定最不常应用的键，能够为缓存中的每个键保护一个 应用计数器。应用计数最小的键是最久未应用的键。
当一个键首次插入到缓存中时，它的应用计数器被设置为 1 (因为 put 操作 )。对缓存中的键执行 get 或 put 操作，应用计数器的值将会递增。
示例：
输出：["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输入：[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释：// cnt(x) = 键 x 的应用计数
// cache=[] 将显示最初一次应用的程序（最右边的元素是最近的）LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1); // cache=[1,_], cnt(1)=1
lFUCache.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lFUCache.get(1); // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lFUCache.put(3, 3); // 去除键 2，因为 cnt(2)=1，应用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lFUCache.get(2); // 返回 -1（未找到）lFUCache.get(3); // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lFUCache.put(4, 4); // 去除键 1，1 和 3 的 cnt 雷同，但 1 最久未应用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lFUCache.get(1); // 返回 -1（未找到）lFUCache.get(3); // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lFUCache.get(4); // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
提醒：
- 0 <= capacity, key, value <=
- 最多调用 次
get和put办法
进阶：你能够为这两种操作设计工夫复杂度为 的实现吗？
根本剖析
前两天咱们刚讲过 146. LRU 缓存机制，简略了解 LRU 就是「移除最久不被应用的元素」。
因而对于 LRU 咱们只须要在应用「哈希表」的同时，保护一个「双向链表」即可：
- 每次产生
get或put的时候就将元素寄存双向链表头部 - 当须要移除元素时，则从双向链表尾部开始移除
LFU 简略了解则是指「移除应用次数起码的元素」，如果存在多个应用次数最小的元素，则移除「最近不被应用的那个」（LRU 规定）。同样的 get 和 put 都算作一次应用。
因而，咱们须要记录下每个元素的应用次数，并且在 的复杂度内「批改某个元素的应用次数」和「找到应用次数最小的元素」。
桶排序 + 双向链表
「咱们能够应用「桶排序」的思路，搭配「双向链表」实现 操作。」
「在 LFUCache 中，咱们保护一个由 Bucket 作为节点的双向链表，每个 Bucket 都有一个 idx 编号，代表以后桶寄存的是「应用了多少次」的键值对」（idx = 1 的桶寄存应用一次的键值对；idx = 2 的桶寄存的是应用两次的键值对 …）。
同时 LFUCache 持有一个「哈希表」，用来记录哪些 key 在哪个桶内。
「在 Bucket 外部则是保护了一条以 Item 作为节点的双向链表，Item 是用作寄存实在键值对的。」
同样的，Bucket 也持有一个「哈希表」，用来记录 key 与 Item 的映射关系。
因而 LFUCache 其实是一个「链表套链表」的数据结构：
对应到 LFUCache 的几种操作：
get：先通过LFUCache持有的哈希表进行查找，如果不存在返回，如果存在找到键值对所在的桶cur：- 调用对应的
cur的remove操作，失去键值对对应的item（移除代表以后键值对应用次数加一了，不会在存在于原来的桶中）。 - 将
item放到idx为 的桶target中（代表代表以后键值对应用次数加一，应该放到新的指标桶中）。 - 如果指标桶
target不存在，则创立；如果原来桶cur移除键值对后为空，则销毁。 - 更新
LFUCache中哈希表的信息。 put：先通过LFUCache持有的哈希表进行查找：- 容量达到数量的话须要调用「编号最小的桶」的
clear操作，在clear操作外部，会从item双向链表的尾部开始移除元素。实现后再执行插入操作。 - 如果存在：找到键值对所在的桶
cur，调用cur的put操作，更新键值对，而后调用LFUCache的get操作实现应用次数加一。 - 如果不存在：先查看容量是否达到数量：
- 插入操作：将键值对增加到 的桶中（代表以后键值对应用次数为），如果桶不存在则创立。
代码：
class LFUCache {
class Item {
Item l, r;
int k, v;
public Item(int _k, int _v) {
k = _k;
v = _v;
}
}
class Bucket {
Bucket l, r;
int idx;
Item head, tail;
Map<Integer, Item> map = new HashMap<>();
public Bucket(int _idx) {
idx = _idx;
head = new Item(-1, -1);
tail = new Item(-1, -1);
head.r = tail;
tail.l = head;
}
void put(int key, int value) {
Item item = null;
if (map.containsKey(key)) {item = map.get(key);
// 更新值
item.v = value;
// 在原来的双向链表地位中移除
item.l.r = item.r;
item.r.l = item.l;
} else {item = new Item(key, value);
// 增加到哈希表中
map.put(key, item);
}
// 减少到双向链表头部
item.r = head.r;
item.l = head;
head.r.l = item;
head.r = item;
}
Item remove(int key) {if (map.containsKey(key)) {Item item = map.get(key);
// 从双向链表中移除
item.l.r = item.r;
item.r.l = item.l;
// 从哈希表中移除
map.remove(key);
return item;
}
return null; // never
}
Item clear() {
// 从双向链表尾部找到待删除的节点
Item item = tail.l;
item.l.r = item.r;
item.r.l = item.l;
// 从哈希表中移除
map.remove(item.k);
return item;
}
boolean isEmpty() {return map.size() == 0;
}
}
Map<Integer, Bucket> map = new HashMap<>();
Bucket head, tail;
int n;
int cnt;
public LFUCache(int capacity) {
n = capacity;
cnt = 0;
head = new Bucket(-1);
tail = new Bucket(-1);
head.r = tail;
tail.l = head;
}
public int get(int key) {if (map.containsKey(key)) {Bucket cur = map.get(key);
Bucket target = null;
if (cur.r.idx != cur.idx + 1) {
// 指标桶空缺
target = new Bucket(cur.idx + 1);
target.r = cur.r;
target.l = cur;
cur.r.l = target;
cur.r = target;
} else {target = cur.r;}
// 将以后键值对从以后桶移除，并退出新的桶
Item remove = cur.remove(key);
target.put(remove.k, remove.v);
// 更新以后键值对所在桶信息
map.put(key, target);
// 如果在移除掉以后键值对后，以后桶为空，则将以后桶删除（确保空间是 O(n) 的）// 也确保调用编号最小的桶的 clear 办法，可能无效移除掉一个元素
deleteIfEmpty(cur);
return remove.v;
}
return -1;
}
public void put(int key, int value) {if (n == 0) return;
if (map.containsKey(key)) {
// 元素已存在，批改一下值
Bucket cur = map.get(key);
cur.put(key, value);
// 调用一下 get 实现「应用次数」+ 1
get(key);
} else {
// 容器已满，须要先删除元素
if (cnt == n) {
// 从第一个桶（编号最小、应用次数最小）中进行革除
Bucket cur = head.r;
Item clear = cur.clear();
map.remove(clear.k);
cnt--;
// 如果在移除掉键值对后，以后桶为空，则将以后桶删除（确保空间是 O(n) 的）// 也确保调用编号最小的桶的 clear 办法，可能无效移除掉一个元素
deleteIfEmpty(cur);
}
// 须要将以后键值对减少到 1 号桶
Bucket first = null;
// 如果 1 号桶不存在则创立
if (head.r.idx != 1) {first = new Bucket(1);
first.r = head.r;
first.l = head;
head.r.l = first;
head.r = first;
} else {first = head.r;}
// 将键值对增加到 1 号桶
first.put(key, value);
// 更新键值对所在桶信息
map.put(key, first);
// 计数器加一
cnt++;
}
}
void deleteIfEmpty(Bucket cur) {if (cur.isEmpty()) {
cur.l.r = cur.r;
cur.r.l = cur.l;
cur = null; // help GC
}
}
}
- 工夫复杂度：各操作均为
- 工夫复杂度：
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.460 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。