题目
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
1
2
3
4
5
6
7
8
9
10
11
|
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
|
题解
题目要求复杂度为O(1)，那么肯定要用到hash表，同时数据的存储是有优先级需求的，要求最近访问的在前，较少访问的在后，这样可以快速的将数据删掉。
数据的存储形式最开始考虑是使用vector，原因是认为vector的index可以简单的与hash表进行关联，通过hash表可以快速的定位到vector中的哪个元素。但后来发现当删除元素，或是调整元素顺序时，vector的时间复杂度明显不是O(1)，要想快速的插入和删除，那么肯定得用list。但若是用list，该怎么和hash表关联起来？到这里，我算是卡壳了，最终打算先用list实现一个复杂度不是O(1)的代码出来，对应的代码如下：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
class LRUCache {
public:
LRUCache(int capacity):max_count(capacity){}
int get(int key) {
int value = -1;
// 遍历list，如果找到，那么保存值并删除
for (auto itr = l.begin(); itr != l.end(); itr++) {
if (itr->first == key) {
value = itr->second;
l.erase(itr);
break;
}
}
// 如果值不为-1，重新插入到链表头
if (value != -1)
l.push_front({ key, value });
// 返回值
return value;
}
void put(int key, int value) {
int count = 0;
// 遍历链表
for (auto itr = l.begin(); itr != l.end(); itr++, count++) {
// 如果能够从链表中找到key，那么删除
if (itr->first == key) {
l.erase(itr);
break;
}
// 如果链表是最大长度，且已经到了链表的最后一个元素
// 那么删除链表的最后一个元素
if (l.size() == max_count && count == l.size() - 1) {
l.erase(itr);
break;
}
}
// 将元素重新插入到链表头
l.push_front({ key, value });
}
private:
int max_count;
std::list<pair<int, int>> l;
};
|
在上面的实现中，获取数据以及插入数据的时间复杂度都是O(N)，提交代码后，当缓存数据很多时，代码运行超时。
最后看了别人的题解，发现还是用链表，但用的是双向链表。而让自己头疼的hash表与链表的关联问题则是自己傻逼了，vector可以存index，链表就不能直接存链表的结点吗？这里的主要原因估计是，自己想的一直是用标准库中的list，其结点对外并不透明，因此也就没有想到这里。
后来试了下，list的迭代器实际上是可以作为节点的，因此hash表中直接存list的迭代器就行了，对应的实现如下：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
class LRUCache {
public:
LRUCache(int capacity) :max_count(capacity) {}
int get(int key) {
// 没找到直接返回-1
if (map.find(key) == map.end()) {
return -1;
}
// 找到值并删除该节点
int value = map[key]->second;
l.erase(map[key]);
// 在头部重新插入该节点，并更新map中该key对应的节点
l.push_front({ key, value });
map[key] = l.begin();
return value;
}
void put(int key, int value) {
// 如果找到key，那么删除节点，并放到链表头
if (map.find(key) != map.end()) {
l.erase(map[key]);
l.push_front({ key, value });
}
// 没有找到key
else {
// 且链表已经是最大长度，那么删除链表尾部的节点
// 同时记得删除map中该key对应的节点
if (l.size() == max_count) {
auto itr = l.back();
map.erase(itr.first);
l.pop_back();
}
// 在链表头添加节点
l.push_front({ key, value });
}
// 更新map中该key对应的节点
map[key] = l.begin();
}
private:
int max_count;
// pair<int,int> -> (key, value)
list<pair<int, int>> l;
// map<int, node> -> (key, node)，迭代器即为节点
unordered_map<int, list<pair<int, int>>::iterator> map;
};
|