相关题目：
460. LFU 缓存
相关文章
LRU 缓存 – 哈希链表
# 460. LFU 缓存
# Python中和 LinkedHashSet 相似的数据结构 OrderedDict
from collections import OrderedDict
class LFUCache:
# key 到 val 的映射，我们后文称为 KV 表
keyToVal = {}
# key 到 freq 的映射，我们后文称为 KF 表
keyToFreq = {}
# freq 到 key 列表的映射，我们后文称为 FK 表
freqToKeys = {}
# 记录最小的频次
minFreq = 0
# 记录 LFU 缓存的最大容量
cap = 0
def __init__(self, capacity: int):
self.keyToVal = {}
self.keyToFreq = {}
self.freqToKeys = {}
self.cap = capacity
self.minFreq = 0
def get(self, key: int) -> int:
if key not in self.keyToVal:
return -1
# 增加 key 对应的 freq
self.increaseFreq(key)
return self.keyToVal[key]
def put(self, key: int, val: int) -> None:
if self.cap <= 0:
return
# 若 key 已存在，修改对应的 val 即可
if key in self.keyToVal:
self.keyToVal[key] = val
# key 对应的 freq 加一
self.increaseFreq(key)
return
# key 不存在，需要插入
# 容量已满的话需要淘汰一个 freq 最小的 key
if self.cap <= len(self.keyToVal):
self.removeMinFreqKey()
# 插入 key 和 val，对应的 freq 为 1
# 插入 KV 表
self.keyToVal[key] = val
# 插入 KF 表
self.keyToFreq[key] = 1
# 插入 FK 表
self.freqToKeys.setdefault(1, OrderedDict())
self.freqToKeys[1].setdefault(key)
# 插入新 key 后最小的 freq 肯定是 1
self.minFreq = 1
def removeMinFreqKey(self):
# freq 最小的 key 列表
keyList = self.freqToKeys.get(self.minFreq)
# 其中最先被插入的那个 key 就是该被淘汰的 key
deletedKey = next(iter(keyList))
# 更新 FK 表
keyList.pop(deletedKey)
if not keyList:
self.freqToKeys.pop(self.minFreq)
# 问：这里需要更新 minFreq 的值吗？
# 更新 KV 表
self.keyToVal.pop(deletedKey)
# 更新 KF 表
self.keyToFreq.pop(deletedKey)
def increaseFreq(self, key: int) -> None:
freq = self.keyToFreq[key]
# 更新 KF 表
self.keyToFreq[key] = freq + 1
# 更新 FK 表
# 将 key 从 freq 对应的列表中删除
self.freqToKeys[freq].pop(key)
# 将 key 加入 freq + 1 对应的列表中
self.freqToKeys.setdefault(freq + 1, OrderedDict())
self.freqToKeys[freq + 1].setdefault(key)
# 如果 freq 对应的列表空了，移除这个 freq
if not self.freqToKeys[freq]:
del self.freqToKeys[freq]
# 如果这个 freq 恰好是 minFreq，更新 minFreq
if freq == self.minFreq:
self.minFreq += 1