LFU 缓存 -- LinkedHashSet

相关题目：
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 = 0def __init__(self, capacity: int):self.keyToVal = {}self.keyToFreq = {}self.freqToKeys = {}self.cap = capacityself.minFreq = 0def get(self, key: int) -> int:if key not in self.keyToVal:return -1# 增加 key 对应的 freqself.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 最小的 keyif 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 肯定是 1self.minFreq = 1def removeMinFreqKey(self):# freq 最小的 key 列表keyList = self.freqToKeys.get(self.minFreq)# 其中最先被插入的那个 key 就是该被淘汰的 keydeletedKey = 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 对应的列表空了，移除这个 freqif not self.freqToKeys[freq]:del self.freqToKeys[freq]# 如果这个 freq 恰好是 minFreq，更新 minFreqif freq == self.minFreq:self.minFreq += 1