> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/niu-ke-0094-kun-nan-she-ji-lfu-huan-cun-jie-gou.md).
# 设计LFU缓存结构
 [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#困难) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#牛客) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#设计) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/04/pages/R5NyOzkn3qAZy7wCx1pS#经典)
> [设计LFU缓存结构\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1)
**问题简述**
```
设计LFU(最近最少频次使用)缓存结构。
```
**思路**
* 定义 `key2cnt` 保存 key 的操作频数；`cnt2key` 保存各频数的 key 队列；
* `cnt2key` 中可以使用 dict（只使用 key）作为有序 set 代替队列，提升删除效率；
* 定义 `refresh`，每次操作后更新 cnt 队列；
* 定义 `least` 保存当前最少的频数；
* 每次有新 key 进来时，重置 `least` 为 1；
* 每次更新 cnt2key 后，如果当前的队列为空且等于 `least`，需要`least += 1`；
Python 写法1
```python
class Solution:
from collections import defaultdict, deque
k: int # 容量
least = 1 # 记录当前最少频次
key2val = dict()
key2cnt = defaultdict(int) # 这个和 key2val 可以合并在一起可以省一组 key，这里为了更清晰分开存储
cnt2key = defaultdict(dict) # 这里实际只用到了 dict 的 key 作为有序 set
def refresh(self, key):
cnt = self.key2cnt[key]
self.cnt2key[cnt].pop(key)
if len(self.cnt2key[cnt]) == 0:
self.cnt2key.pop(cnt)
if self.least == cnt:
self.least += 1
self.key2cnt[key] += 1
self.cnt2key[cnt + 1][key] = None # 因为只用了 key，
def get(self, key):
ret = self.key2val.get(key, -1)
if key in self.key2val:
self.refresh(key)
return ret
def set(self, key, value):
if key not in self.key2val:
# 超容量的情况
if len(self.key2val) >= self.k:
tmp = next(iter(self.cnt2key[self.least]))
# 全部 pop
self.cnt2key[self.least].pop(tmp)
self.key2val.pop(tmp)
self.key2cnt.pop(tmp)
self.key2val[key] = value
self.key2cnt[key] += 1
self.cnt2key[self.key2cnt[key]][key] = None
self.least = 1 # 因为是新的 key，所以显然最少频次将更新为 1
else:
self.refresh(key)
self.key2val[key] = value
def LFU(self , operators: List[List[int]], k: int) -> List[int]:
self.k = k
ret = []
for op in operators:
if op[0] == 1:
self.set(op[1], op[2])
else:
ret.append(self.get(op[1]))
return ret
```
* 写法 2 的区别仅在于将 `key2cnt` 和 `key2val` 合并在一起，省了一组 `key` 的空间；
Python 写法2
```python
class Solution:
from collections import defaultdict, deque
k: int # 容量
least = 1 # 记录当前最少频次
key2cnt = dict() # 出了保存频次，也保存了值
cnt2key = defaultdict(dict) # 这里实际只用到了 dict 的 key 作为有序 set
# 这里也可以使用队列，但是删除效率应该不如 set
def refresh(self, key):
cnt = self.key2cnt[key][0]
self.cnt2key[cnt].pop(key)
if len(self.cnt2key[cnt]) == 0:
self.cnt2key.pop(cnt)
if self.least == cnt:
self.least += 1
self.key2cnt[key][0] += 1
self.cnt2key[cnt + 1][key] = None # 因为只用了 key，
def get(self, key):
ret = self.key2cnt[key][1] if key in self.key2cnt else -1
if key in self.key2cnt:
self.refresh(key)
return ret
def set(self, key, value):
if key not in self.key2cnt:
# 超容量的情况
if len(self.key2cnt) >= self.k:
tmp = next(iter(self.cnt2key[self.least]))
# 全部 pop
self.cnt2key[self.least].pop(tmp)
self.key2cnt.pop(tmp)
cnt = 1
self.key2cnt[key] = [cnt, value]
self.cnt2key[cnt][key] = None
self.least = 1 # 因为是新的 key，所以显然最少频次将更新为 1
else:
self.refresh(key)
self.key2cnt[key][1] = value
def LFU(self , operators: List[List[int]], k: int) -> List[int]:
self.k = k
ret = []
for op in operators:
if op[0] == 1:
self.set(op[1], op[2])
else:
ret.append(self.get(op[1]))
return ret
```