460. LFU 缓存
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
实现
LFUCache 类：LFUCache(int capacity)- 用数据结构的容量capacity初始化对象
int get(int key)- 如果键key存在于缓存中，则获取键的值，否则返回1。
void put(int key, int value)- 如果键key已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量capacity时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时，它的使用计数器被设置为
1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。函数
get 和 put 必须以 O(1) 的平均时间复杂度运行。示例：
输入： ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] 输出： [null, null, null, 1, null, -1, 3, null, -1, 3, 4] 解释： // cnt(x) = 键 x 的使用计数 // cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的） LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // 返回 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小 // cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // 返回 -1（未找到） lfu.get(3); // 返回 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用 // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // 返回 -1（未找到） lfu.get(3); // 返回 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // 返回 4 // cache=[3,4], cnt(4)=2, cnt(3)=3
提示：
0 <= capacity <= 104
0 <= key <= 105
0 <= value <= 109
- 最多调用
2 * 105次get和put方法
通过次数39,694提交次数91,214
法 1
思路
三个hashmap:
- map：用来存储 本来的键值对
- count：用来统计每个key的使用频率
- lru：模拟LRU，key为使用频率，val为列表，存放该使用频率下的缓存key，按照访问时间存储，列表末尾的为最近访问的。所以要删除的话，应该删除列表头部的。由于该列表会从头删节点，故采用deque()
可以再维护一个全局变量，存储着 最低访问频率 的频率值，这样删除的时候，不用再从头找一遍最低频率值了。
题解
class LFUCache: def __init__(self, capacity: int): self.capacity = capacity self.map = {} self.count = {} self.lru = {} self.lru[1] = deque() self.min_count = 1 def get(self, key: int) -> int: if key not in self.map: return -1 # 改变当前 key 的 最近使用位置 和 使用频率 cur_count = self.count[key] self.lru[cur_count].remove(key) # 更新最低使用频率的 频率值 if (cur_count == self.min_count and len(self.lru[cur_count]) == 0): self.min_count += 1 self.count[key] += 1 if cur_count + 1 not in self.lru: self.lru[cur_count+1] = deque() self.lru[cur_count+1].append(key) return self.map[key] def put(self, key: int, value: int) -> None: if key in self.map: self.map[key] = value # 改变当前 key 的 最近使用位置 和 使用频率 self.get(key) else: if self.capacity == 0: return # 在 插入 之前删除 if len(self.map) >= self.capacity: # 找到 最不经常使用的 次数 # self.min_count = min(self.count.values()) # 找到最不经常使用 且 最久未使用 delet_key = self.lru[self.min_count].popleft() # 删除 del self.map[delet_key] del self.count[delet_key] self.map[key] = value self.count[key] = 1 self.lru[1].append(key) self.min_count = 1 # Your LFUCache object will be instantiated and called as such: # obj = LFUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value)