题目描述
思路解析动画文字版
如果每次淘汰都从头扫一遍找「频次最小」的键,缓存一大就慢成一团。我们要的是O(1) 直接拿到该淘汰谁。
三张表配合:① 键→值 ② 键→频次 ③ 频次→该频次的键队列(LRU 顺序)。再加一个 minFreq。这样取「该淘汰谁」永远是 O(1)。
接下来上排格子代表容量为 2 的两个槽,格子里写键;下方哈希表是频次桶。盯住 minFreq 和桶里的排队顺序。
put(1,1) · 放入键 1：放入新键 1,值 1。新键频次从 1 起步,丢进 freq 1 桶。当前只有它,minFreq = 1。另一个槽还空着(灰)。
put(2,2) · 放入键 2：再放键 2,频次也是 1,排进 freq 1 桶,排在 1 的后面(它更新)。两个槽都满了。
get(1) → 找键 1：get(1):键 1 在缓存里,返回它的值 1。但访问算一次使用,接下来要把它的频次 +1。
get(1) · 频次 1 → 2：键 1 升级:从 freq 1 桶移出,放进新的 freq 2 桶。freq1 桶现在只剩键 2。
get(1) · minFreq 还是 1：要不要更新 minFreq?freq1 桶还有键 2,所以 minFreq 仍然是 1。记住:只有最小桶被搬空时 minFreq 才上移。
put(3,3) · 缓存已满!：put(3,3):缓存已满,得先淘汰。看 minFreq = 1 桶,取它的队头(最久未用)—— 正是键 2。
put(3,3) · 淘汰键 2：键 2 被淘汰出局,腾出一个槽。freq1 桶被搬空了,整桶删掉。现在最低频次的桶是 freq2。
put(3,3) · 放入键 3：放入新键 3,频次从 1 起步,进 freq1 桶。关键:任何新键都让 minFreq 立刻重置为 1(因为它就是最低频)。
get(2) → 找键 2：get(2):键 2 刚被淘汰了,缓存里找不到 → 返回 -1。这一步什么都不改。
get(3) → 找键 3：get(3):命中,返回值 3。和 get(1) 一样,接下来给它频次 +1。
get(3) · 频次 1 → 2：键 3 从 freq1 移到 freq2 桶,排在键 1 后面(3 更新)。这下 freq1 桶空了,而且它正是 minFreq 桶 → minFreq 上移到 2!
put(4,4) · 又满了!：put(4,4):又满了。这次 minFreq = 2 桶里有两个键(1 和 3,频次都是 2)。频次平手,就看谁最久没碰 —— 队头是键 1(3 刚被 get 过)。
put(4,4) · 淘汰键 1：淘汰队头键 1(它和键 3 频次都是 2,但更久没被访问)。freq2 桶现在只剩键 3。这一步就是 LFU 里藏的 LRU 规则。
put(4,4) · 放入键 4：放入新键 4,频次 1,进 freq1 桶,minFreq 又重置为 1。注意:键 3 还稳稳待在 freq2 桶里没动。
get(1) → 找键 1：get(1):键 1 上一步被淘汰了 → 返回 -1。
get(3) → 找键 3：get(3):命中返回 值 3,频次升到 3,移到 freq3 桶。freq1 桶还有键 4,所以 minFreq 仍是 1。
get(4) → 找键 4：get(4):命中返回 值 4,频次升到 2,freq1 桶又被搬空 → minFreq 上移到 2。全程返回值依次是 1, -1, 3, -1, 3, 4。
全程回放 · 答案：整串操作走完,缓存里留下用得多的键 3 和键 4。get 的返回序列正是 1, -1, 3, -1, 3, 4 —— 和官方答案一致。
再演一手 · put(5,5)：再加一手 put(5,5) 看个反直觉点:虽然键 4 是最近才 get 过的,但它频次(2)比键 3(3)低 —— LFU 先看频次,所以照样淘汰键 4。
put(5,5) · 淘汰键 4 放入键 5：键 4 被淘汰,键 5 入桶 freq1,minFreq 重置为 1。频次最高的键 3 反而留了下来 —— 这正是 LFU 和 LRU 的本质区别:LRU 会保留最近用的键 4,LFU 保留用得最多的键 3。
雷区实演 · 插新键忘了重置 minFreq：假如插入新键 4(频次 1)后没把 minFreq 重置为 1,minFreq 还停在 2。下次淘汰就会从 freq2 桶踢掉频次更高的键 3 —— 把用得多的反而淘汰了,大错。
边界三连：先想清 0 容量、更新已存在键、频次平手三种边界,代码就不会漏。
面试追问：把 minFreq 的更新时机、桶内 LRU、和 LRU 的区别讲清楚,是这题面试的得分点。
参考代码
from collections import defaultdict, OrderedDictclass LFUCache: def __init__(self, capacity): self.cap = capacity self.minFreq = 0 self.kv = {} # key -> value self.kf = {} # key -> freq self.fk = defaultdict(OrderedDict) # freq -> {key: None} def _touch(self, key): # 频次 +1,挪桶 f = self.kf[key] del self.fk[f][key] if not self.fk[f]: del self.fk[f] if self.minFreq == f: self.minFreq += 1 self.kf[key] = f + 1 self.fk[f + 1][key] = None def get(self, key): if key not in self.kv: return -1 self._touch(key) return self.kv[key] def put(self, key, value): if self.cap == 0: return if key in self.kv: self.kv[key] = value; self._touch(key); return if len(self.kv) >= self.cap: # 淘汰 old, _ = self.fk[self.minFreq].popitem(last=False) del self.kv[old]; del self.kf[old] self.kv[key] = value; self.kf[key] = 1 self.fk[1][key] = None; self.minFreq = 1复杂度
- get / put 时间：O(1)，哈希表查键 O(1);挪桶是双向链表/有序集合的删尾插头 O(1);淘汰直接取 minFreq 桶队头 O(1)。全程没有遍历。
- 空间复杂度：O(capacity)，三张表里的键值数量都不超过容量,频次桶总元素数也 = 缓存中键数 → O(capacity)。
易错点
面试追问把动画讲成自己的话
追问minFreq 什么时候 +1?什么时候重置为 1?
追问频次相同的多个键怎么决定淘汰谁?
追问和 LRU(LC146)的核心区别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题