146. LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache
类:
LRUCache(int capacity)
以 正整数 作为容量 capacity
初始化 LRU 缓存
int get(int key)
如果关键字 key
存在于缓存中,则返回关键字的值,否则返回 -1
。
void put(int key, int value)
如果关键字 key
已经存在,则变更其数据值 value
;如果不存在,则向缓存中插入该组 key-value
。如果插入操作导致关键字数量超过 capacity
,则应该 逐出 最久未使用的关键字。
函数 get
和 put
必须以 O(1)
的平均时间复杂度运行。
示例:
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示:
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
- 最多调用
2 * 105
次 get
和 put
解题思路
什么是 LRU?
思路:单链表
- put 操作:
- 如果节点不存在,直接把节点插入到头部
- 如果节点存在,则把这个节点从链表中删除,并且更新值再插入到头部
- 如果插入时,超过最大容量,则将链表的最后一个节点删除,并且将新节点插入到头部
- get 操作:
- 如果节点存在,则返回,并且将节点删除以及插入到链表头部
- 如果节点不存在,则直接返回-1,没有额外操作
- 该方法下,put 和 get 操作的时间复杂度都为 O(n),并不符合题目所要求的 O(1)
- 那么,如何优化?
- 加哈希表,省去 get 操作遍历的过程;但实际上,时间复杂度还是 O(n)。
- 为什么?
- 因为不管是 put 操作还是 get 操作,都有删除操作,虽然加入哈希表能够省去遍历的过程,但是不能优化删除操作。删除节点需要找到其前驱节点,那么这个寻找前驱节点的过程也需要 O(n)的时间复杂度。
- 如何省去寻找节点的前驱节点这个过程呢?
- 可以使用双向链表,从而节点本身就包含了其前驱节点和后驱节点的信息,不用再去寻找了,以此达到 O(1)的要求。
- 双向链表 + 哈希表(最终的解决方案)