LFU 缓存
LFU Cache
题目详情
问题：LFU 缓存
考察：哈希表、链表、设计
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/lfu-cache
英文原题
Problem: LFU Cache
Patterns: Hash Table, Linked List, Design
Recency: 6mo
Link: https://leetcode.com/problems/lfu-cache
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：维护 key 到节点的映射，以及频次到有序链表的映射。get/put 命中时把节点从旧频次链表移到新频次链表；淘汰时从最小频次链表尾部删除最久未使用节点。
复杂度：get/put 平均 O(1)，空间 O(capacity)。
英文解析
Approach: Maintain a map from key to node and a map from frequency to an ordered list of nodes. On every access, move the node to the next frequency list. When evicting, remove the least recently used node from the current minimum-frequency list.
Complexity: Average `get`/`put`, space .