当前位置：首页 > news >正文

LeetCode 460 - LFU 缓存

news 2026/6/12 0:11:04

文章目录

- 摘要
- 描述
- 题解答案
- 题解代码分析
- - 节点需要存什么信息？
  - 为什么要用「频次 → 双向链表」？
  - LFUCache 的核心结构
  - get 操作怎么做？
  - put 操作的关键点
  - 更新频次是整个设计的核心
- 示例测试及结果
- 与实际场景结合
- 时间复杂度
- 空间复杂度
- 总结

摘要

LFU 缓存是缓存算法里的“进阶关卡”。

LRU 大家都很熟，但 LFU 往往是很多人刷 LeetCode 时第一次真正感受到：
“原来 O(1) 的设计不是写得快，而是数据结构选得对。”

这道题不只是让你写一个缓存，而是在逼你回答三个工程级问题：

怎么在 O(1) 内找到最少使用的 key？
使用次数相同时，怎么再按 LRU 淘汰？
get / put 都要是 O(1)，不能靠排序、遍历硬撑。

描述

题目要求你实现一个 LFUCache，支持：

get(key)
- 存在：返回 value，并且使用次数 +1
- 不存在：返回 -1
put(key, value)
- key 已存在：更新 value，并且使用次数 +1
- key 不存在：
  - 如果缓存没满，直接插
  - 如果缓存满了：
    - 先淘汰使用次数最少
    - 如果次数相同，淘汰最久没用的

并且有一个非常重要的硬指标：

get和put的平均时间复杂度必须是O(1)

这直接排除了所有“排序 / 每次扫描一遍”的方案。

题解答案

真正能跑通并满足 O(1) 的解法，核心是三层结构：

key → Node 映射
freq → 双向链表映射
一个全局的minFreq

一句话总结：

用 HashMap 快速定位节点，用「频次分桶 + LRU 链表」来控制淘汰顺序。

题解代码分析

节点需要存什么信息？

每一个缓存项，至少要知道：

key
value
当前使用频率 freq
在链表里的前后指针（为了 O(1) 删除）

classNode{letkey:Intvarvalue:Intvarfreq:Int=1varprev:Node?varnext:Node?init(_key:Int,_value:Int){self.key=keyself.value=value}}

为什么要用「频次 → 双向链表」？

因为 LFU 有一个隐藏条件：

同一个频次下，要按 LRU 淘汰

所以每个频次桶，本质上是一个LRU 链表。

classDoublyLinkedList{lethead=Node(0,0)lettail=Node(0,0)varsize=0init(){head.next=tail tail.prev=head}funcaddToHead(_node:Node){node.next=head.next node.prev=head head.next?.prev=node head.next=node size+=1}funcremove(_node:Node){node.prev?.next=node.next node.next?.prev=node.prev size-=1}funcremoveLast()->Node?{guardsize>0,letlast=tail.prev,last!==headelse{returnnil}remove(last)returnlast}}

LFUCache 的核心结构

classLFUCache{privateletcapacity:IntprivatevarminFreq=0privatevarkeyToNode=[Int:Node]()privatevarfreqToList=[Int:DoublyLinkedList]()

keyToNode：O(1) 找节点
freqToList：O(1) 找某个频次的 LRU 链表
minFreq：O(1) 知道该淘汰谁

get 操作怎么做？

核心逻辑只有三步：

查 key 是否存在
从旧 freq 链表中移除
freq +1，放进新链表

funcget(_key:Int)->Int{guardletnode=keyToNode[key]else{return-1}updateFreq(node)returnnode.value}

put 操作的关键点

capacity 为 0，直接返回
key 已存在：更新 value + 更新 freq
key 不存在：
- 如果满了：
  - 从minFreq对应的链表里，删最久未使用
- 插入新节点，freq = 1

funcput(_key:Int,_value:Int){ifcapacity==0{return}ifletnode=keyToNode[key]{node.value=valueupdateFreq(node)return}ifkeyToNode.count==capacity{ifletlist=freqToList[minFreq],letremoved=list.removeLast(){keyToNode.removeValue(forKey:removed.key)}}letnewNode=Node(key,value)keyToNode[key]=newNodeletlist=freqToList[1]??DoublyLinkedList()list.addToHead(newNode)freqToList[1]=list minFreq=1}

更新频次是整个设计的核心

privatefuncupdateFreq(_node:Node){letfreq=node.freqifletlist=freqToList[freq]{list.remove(node)iffreq==minFreq&&list.size==0{minFreq+=1}}node.freq+=1letnewList=freqToList[node.freq]??DoublyLinkedList()newList.addToHead(node)freqToList[node.freq]=newList}

这里做了三件事：

从旧频次链表移除
如果刚好是 minFreq 且链表空了，更新 minFreq
插入新频次链表头部

示例测试及结果

letlfu=LFUCache(2)lfu.put(1,1)lfu.put(2,2)print(lfu.get(1))// 1lfu.put(3,3)print(lfu.get(2))// -1print(lfu.get(3))// 3lfu.put(4,4)print(lfu.get(1))// -1print(lfu.get(3))// 3print(lfu.get(4))// 4