题目描述
请为LRU缓存设计一个数据结构。支持两种操作:get和put。
- get(key) - 如果key在缓存中,则返回key对应的值(保证是正的);否则返回-1;
- put(key, value) - 如果key在缓存中,则更新key对应的值;否则插入(key, value),如果缓存已满,则先删除上次使用时间最老的key。
进一步:
能否使用两个操作都是 $O(1)$ 时间复杂度的算法?
样例
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 删除 key 2
cache.get(2); // 返回 -1 (没找到)
cache.put(4, 4); // 删除 key 1
cache.get(1); // 返回 -1 (没找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
算法
(哈希 + 队列维护) $O(1)$
模拟cache操作。首先,需要维护一个key_val_dict
,来存储key和value。同时需要维护每个key被访问到的时间,因此维护一个全局time值表示这是第几次被查询,每次put/get时time+1,并且维护一个key_time_dict
来记录每个key的最新访问时间。
这题难点在于如何迅速找到要删除的元素,可以利用队列先进先出的特性,每次访问到一个key,就把这个key和当前time压入队列,而需要删除时把堆顶元素拿出来就行了。
但是有可能弹出的元素已经“过时”了(比如在time = 1
时访问到了key,在之后time = 3
的时候又访问了这个key,但是这个keytime = 1
的访问记录还在堆里呢)。因此需要判断一下,判断从堆顶弹出来的元素的time与key_time_dict
维护的key的最新访问时间是否能对上,如果对不上说明已经过时了,这个key被更新的时间访问过。因此需要一直弹出过时的元素,直到找到没过时的元素,然后删除这个key。
时间复杂度
dict的查询速度是$O(1)$,因此查询的复杂度是$O(1)$。
而对于插入来说,如果不用删除元素,复杂度为$O(1)$。而需要删除元素时,所有put操作导致的总共的删除的元素的个数小于等于总共get/put操作的次数(因为每操作一次会往队列插入一个元素),因此平均下来每次插入都是$O(1)$的复杂度。
空间复杂度
最坏情况下,所有插入的元素都可能在队列中,因此最坏空间复杂度为$O(N)$(N是操作的次数)。
参考文献
Python 代码
class LRUCache:
def __init__(self, capacity: int):
self.key_val_dict = {} # 存key value
self.capacity = capacity
self.queue = collections.deque() # 用于找到要删除的元素
self.key_time_dict = {} # 用于记录每个key最新访问时间
self.time = 0
def update(self, key): # 更新key访问时间
self.queue.append((key, self.time))
self.key_time_dict[key] = self.time
def get(self, key: int) -> int:
self.time += 1
if key in self.key_val_dict:
self.update(key)
return self.key_val_dict[key]
else:
return -1
def put(self, key: int, value: int) -> None:
self.time += 1
if key in self.key_val_dict:
self.key_val_dict[key] = value
self.update(key)
else:
if len(self.key_val_dict) < self.capacity: # 还有空间 直接插入即可
self.key_val_dict[key] = value
self.update(key)
else:
to_del_key, to_del_time = self.queue.popleft()
# 找删除的元素
while self.key_time_dict[to_del_key] != to_del_time and len(self.queue) > 0:
to_del_key, to_del_time = self.queue.popleft()
del self.key_val_dict[to_del_key] # 删除
del self.key_time_dict[to_del_key]
self.key_val_dict[key] = value
self.update(key)