LeetCode 460. LFU 缓存
题目描述
题意分析
实现固定容量的缓存：
get(key)命中时返回值，未命中返回-1；put(key, value)更新已有键或插入新键。只有插入新键且容量已满时才淘汰，更新已有键不需要腾出空间。淘汰先比较使用频次，频次最低者优先；若频次相同，再淘汰最久未使用的键。新键频次为
1，命中的get和更新已有键的put都让频次加一，并算作最近一次使用；未命中的查询不改变缓存。两个操作都要求平均 $O(1)$ 时间，因此不能每次遍历所有键来寻找最低频次或最旧记录。
解法：哈希表 + 频率链表
核心思路
[!blue]
需要同时解决按键查找、按频次分组和同频次按新旧淘汰。
nodes把键映射到节点，节点保存值、频次和前后指针；lists把频次映射到双向链表，每条链表只存放该频次的节点。得到节点后，可以直接摘除，不必扫描链表。同频链表的头部是最近使用者，尾部是最久未使用者。一个节点每次被使用都会升频，并插入新频次链表的头部；仍留在该链表里的其他节点都比这次访问更早，所以插到头部正好维持最近使用顺序。头尾哨兵不存放真实缓存项，只统一空链表和首尾节点的连接操作。
用
minFreq保存当前最低非空频次。缓存满时，只需从lists[minFreq]的尾部取出一个节点，并同步从nodes删除，便同时满足“频次最低”和“同频最旧”两个条件。命中的查询与更新共用
increase：先从频次f的旧链表摘除节点，再将它的频次改为f + 1并插到新链表头。如果旧链表仍有节点，最低频次不变；如果旧链表空了但f不是最低频次，也不影响minFreq。只有旧链表为空且
f == minFreq时，最低频次才加一。原来所有节点的频次都不小于f，移走唯一的f节点后，其余节点至少为f + 1，而刚升频的节点恰好达到f + 1，所以新的最小值必然就是它，无需搜索下一只桶。插入新键是另一种情况：必要时先淘汰，再插入频次为
1的节点，并直接令minFreq = 1。每次节点迁移或淘汰后都删除已经空掉的频次链表，避免访问次数增长时留下大量空桶。
解题步骤
- 初始化节点表、频次桶表和
minFreq；容量为 0 时，put直接返回。get(key)未命中返回-1；命中则执行升频，再返回节点值。put(key, value)命中时更新值并升频。更新也算一次访问，不能把频次重置为 1。- 插入新 key 前若容量已满，从
minFreq桶尾删除最旧节点，并从节点表同步删除。- 新节点以
freq = 1插入桶头，同时设置minFreq = 1。- 升频按“保存旧频次并摘除节点 → 删除空桶，必要时修正
minFreq→freq++→ 插入新桶头部”的顺序执行。
代码实现
class LFUCache {
private final int capacity;
private int minFreq;
private final Map<Integer, Node> nodes = new HashMap<>();
private final Map<Integer, DoubleList> lists = new HashMap<>();
public LFUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
Node node = nodes.get(key);
if (node == null) {
return -1;
}
increase(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
Node node = nodes.get(key);
if (node != null) {
node.value = value;
increase(node);
return;
}
if (nodes.size() == capacity) {
DoubleList list = lists.get(minFreq);
// 最低频桶中，尾节点是最久未使用者。
Node removed = list.removeLast();
nodes.remove(removed.key);
if (list.isEmpty()) {
lists.remove(minFreq);
}
}
node = new Node(key, value);
nodes.put(key, node);
lists.computeIfAbsent(1, ignored -> new DoubleList()).addFirst(node);
// 新插入节点从频率一开始，直接成为最低频候选。
minFreq = 1;
}
private void increase(Node node) {
int oldFreq = node.freq;
DoubleList oldList = lists.get(oldFreq);
// 先从旧频率桶摘除，再修改节点频率。
oldList.remove(node);
if (oldList.isEmpty()) {
lists.remove(oldFreq);
if (oldFreq == minFreq) {
// 旧最低桶已空，刚升频的节点保证下一频率非空。
minFreq++;
}
}
node.freq++;
lists.computeIfAbsent(node.freq, ignored -> new DoubleList()).addFirst(node);
}
private static class Node {
int key;
int value;
int freq = 1;
Node pre;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private static class DoubleList {
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
DoubleList() {
head.next = tail;
tail.pre = head;
}
void addFirst(Node node) {
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
void remove(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
Node removeLast() {
Node node = tail.pre;
remove(node);
return node;
}
boolean isEmpty() {
return head.next == tail;
}
}
}
type LFUCache struct {
capacity int
minFreq int
nodes map[int]*lfuNode
lists map[int]*lfuList
}
type lfuNode struct {
key int
value int
freq int
pre *lfuNode
next *lfuNode
}
type lfuList struct {
head *lfuNode
tail *lfuNode
}
func Constructor(capacity int) LFUCache {
return LFUCache{
capacity: capacity,
nodes: make(map[int]*lfuNode),
lists: make(map[int]*lfuList),
}
}
func (this *LFUCache) Get(key int) int {
node := this.nodes[key]
if node == nil {
return -1
}
this.increase(node)
return node.value
}
func (this *LFUCache) Put(key int, value int) {
if this.capacity == 0 {
return
}
if node := this.nodes[key]; node != nil {
node.value = value
this.increase(node)
return
}
if len(this.nodes) == this.capacity {
list := this.getList(this.minFreq)
// 最低频桶中，尾节点是最久未使用者。
removed := list.removeLast()
delete(this.nodes, removed.key)
if list.isEmpty() {
delete(this.lists, this.minFreq)
}
}
node := &lfuNode{key: key, value: value, freq: 1}
this.nodes[key] = node
this.getList(1).addFirst(node)
// 新插入节点从频率一开始，直接成为最低频候选。
this.minFreq = 1
}
func (this *LFUCache) increase(node *lfuNode) {
oldFreq := node.freq
oldList := this.getList(oldFreq)
// 先从旧频率桶摘除，再修改节点频率。
oldList.remove(node)
if oldList.isEmpty() {
delete(this.lists, oldFreq)
if oldFreq == this.minFreq {
// 旧最低桶已空，刚升频的节点保证下一频率非空。
this.minFreq++
}
}
node.freq++
this.getList(node.freq).addFirst(node)
}
func (this *LFUCache) getList(freq int) *lfuList {
if this.lists[freq] == nil {
head := &lfuNode{}
tail := &lfuNode{}
head.next = tail
tail.pre = head
this.lists[freq] = &lfuList{head: head, tail: tail}
}
return this.lists[freq]
}
func (list *lfuList) addFirst(node *lfuNode) {
node.next = list.head.next
node.pre = list.head
list.head.next.pre = node
list.head.next = node
}
func (list *lfuList) remove(node *lfuNode) {
node.pre.next = node.next
node.next.pre = node.pre
}
func (list *lfuList) removeLast() *lfuNode {
node := list.tail.pre
list.remove(node)
return node
}
func (list *lfuList) isEmpty() bool {
return list.head.next == list.tail
}
复杂度分析
- 时间复杂度：
get、put的平均时间复杂度均为 $O(1)$。每次只进行常数次哈希查找和链表摘插，minFreq也只做一步修正。- 空间复杂度：$O(\text{capacity})$。每个缓存项对应一个节点；每只保留的频次桶至少有一个节点，因此桶数也不超过缓存项数。空桶及时删除，空间不随历史访问次数增长。
关键点总结
[!green]
- 两张哈希表分别解决“按 key 定位”和“按频次分组”，桶内双向链表解决同频时的 LRU 淘汰。
- 最低桶被升频搬空时，迁移的节点保证下一频次桶非空，因此
minFreq只需加一；新节点插入时重置为 1。get和更新已有 key 都必须升频，统一复用increase可避免两条逻辑不同步。
易错点总结
[!yellow]
- 升频时必须先从旧桶删除，再修改
freq；否则会去错误的桶操作链表。- 只有旧桶频次等于
minFreq且删除后为空时才能minFreq++；仍有最低频节点留下时不能改变它。- 淘汰和插入顺序不能反：若先插入并重置最低频次，新节点可能成为本轮被淘汰的对象。
- 淘汰节点时要同时从链表和节点表删除；空桶也应删除，否则空间会随历史频次增长。
- 新节点必须令
minFreq = 1；capacity = 0必须直接返回，避免从不存在的桶中淘汰。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 146. LRU 缓存 | 中等 | 原题只按最近使用时间淘汰，本题优先比较使用频率，同频时再比较新旧。 |
| 432. 全 O(1) 的数据结构 | 困难 | 同样使用哈希定位和双向频次桶，原题直接查询频次极值，本题还维护缓存容量与同频访问顺序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！