题目描述
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用)
缓存机制。它应该支持以下操作: 获取数据 get
和 写入数据 put
。
获取数据 get(key)
- 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value)
- 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
进阶:
你是否可以在$O(1)$ 时间复杂度内完成这两种操作?
示例:
1 | cache = LRUCache(2) |
分析
看到题目要我们实现一个可以存储key-value形式数据的数据结构,并且可以记录最近访问的key值。首先想到的就是用字典来存储key-value结构,这样对于查找操作时间复杂度就是$O(1)$。
但是因为字典本身是无序的,所以我们还需要一个类似于队列的结构来记录访问的先后顺序,这个队列需要支持如下几种操作:
- 在末尾加入一项
- 去除最前端一项
- 将队列中某一项移到末尾
首先考虑列表结构。
对于列表加入有append()
,删除有pop()
操作,这两个都是$O(1)$的时间复杂度。而对于将队列中某一项移到末尾,因为列表中存储的是哈希表的key,考虑这样一种情况:
1 | # 操作 |
此时我们再进行cache.put(2, 2)
的操作,因为2已经存在在哈希表中,这说明队列中已经存在值为2的元素,那么问题来了,如何在常数时间内把它挑出来移到队尾呢?
答案是不行,所以用列表无法实现常数时间复杂度。
之后再考虑单链表。
对于单链表,哈希表的结构类似于{key: ListNode(value)}
,即键所对应的是一个节点地址,节点的值是value。对于链表,遇到上面那种情况时可以在常数的时间内找到对应的节点,但是如果想将它移到尾部则需要从头遍历到该节点才能保证链表不断,对于这种情况需要的时间复杂度也是$O(n)$
为了解决移到末尾这个问题,需要使用双链表来记录,结构大概如下图所示:
graph LR subgraph 哈希表 hash1("hashmap[1]") hash2("hashmap[2]") hash1 -.- hash2 end subgraph 双向链表 head node1 node2 tail end hash1-->node1 hash2-->node2 head-->node1 node1-->node2 node2-->tail tail-->node2 node2-->node1 node1-->head
这个实在是太丑了没眼看,以后不用了
代码
1 | class ListNode: |