0146：LRU 缓存（★）

Ian

2015-05-26 约 634 字预计阅读 2 分钟次阅读

力扣第 146 题

题目

请你设计并实现一个满足 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 <= 10⁵
最多调用 2 * 10⁵ 次 get 和 put

分析

#1

先考虑通用方法，用有序集合维护关键字的顺序:

维护时间戳 t
有序集合 sl 维护 (t,key)
哈希表维护 d 维护 key 对应的 t 和 value
get 和 put 时模拟操作即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class LRUCache:

    def __init__(self, capacity: int):
        from sortedcontainers import SortedList
        self.sl = SortedList()
        self.m = capacity
        self.t = 0
        self.d = {}

    def get(self, key: int) -> int:
        if key not in self.d:
            return -1
        t,x = self.d[key]
        self.sl.remove((t,key))
        self.sl.add((self.t,key))
        self.d[key] = (self.t,x)
        self.t += 1
        return x

    def put(self, key: int, value: int) -> None:
        if key in self.d:
            t,_ = self.d[key]
            self.sl.remove((t,key))
        elif len(self.sl)==self.m:
            _,x = self.sl.pop(0)
            self.d.pop(x)
        self.sl.add((self.t,key))
        self.d[key] = (self.t,value)
        self.t += 1

578 ms

#2

要求 O(1) 时间完成 put() 和 get()，可以用双向链表+哈希表来实现
python 可以用 OrderedDict 方便地实现

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class LRUCache:

    def __init__(self, capacity: int):
        self.d = OrderedDict()
        self.m = capacity

    def get(self, key: int) -> int:
        if key not in self.d:
            return -1
        self.d.move_to_end(key)
        return self.d[key]

    def put(self, key: int, value: int) -> None:
        if key in self.d:
            self.d.move_to_end(key)
        elif len(self.d)==self.m:
            self.d.popitem(last=False)
        self.d[key] = value

382 ms

目录

0146：LRU 缓存（★）

题目

分析

#1

#2

解答