146. LRU 缓存
一句话套路哈希表 + 双向链表,get/put 都 O(1)
题目描述
请你设计并实现一个满足 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 <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
思路
空间
O(capacity)思路
数据结构 = 哈希表 + 双向链表:
- · 双向链表保存「使用顺序」,表头最新、表尾最旧,淘汰只看表尾。
- · 哈希表 key -> 链表迭代器,保证 get 能
O(1)找到结点。 - · splice 是
O(1)把结点搬到表头的操作,不用 new/delete,也不会让迭代器失效。
延伸
LFU 需要「频次桶 + 每桶内 LRU」,见 Q460。
图解
容量 2,顺序操作 put(1,1) → put(2,2) → get(1) → put(3,3)。只有 get/put 命中时把该键移到「最近使用」端;put 新键且已满时踢掉「最久未用」端。
C++17 题解
namespace lc0146 {
class LRUCache {
public:
explicit LRUCache(int capacity) : cap_(capacity) {}
int get(int key) {
auto it = pos_.find(key);
if (it == pos_.end()) return -1;
order_.splice(order_.begin(), order_, it->second); // 提到表头
return it->second->second;
}
void put(int key, int value) {
if (cap_ <= 0) return; // 题面保证 capacity ≥ 1;否则下面的 order_.back() 会在空表上 UB
auto it = pos_.find(key);
if (it != pos_.end()) {
it->second->second = value;
order_.splice(order_.begin(), order_, it->second);
return;
}
if ((int)order_.size() == cap_) { // 先淘汰,再插入
pos_.erase(order_.back().first);
order_.pop_back();
}
order_.emplace_front(key, value);
pos_[key] = order_.begin();
}
private:
int cap_;
std::list<std::pair<int, int>> order_; // (key, value),front = 最近使用
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> pos_;
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0146::LRUCache c(2);
c.put(1, 1);
c.put(2, 2);
CHECK_EQ(c.get(1), 1);
c.put(3, 3); // 淘汰最久未用的 2
CHECK_EQ(c.get(2), -1);
c.put(4, 4); // 淘汰 1
CHECK_EQ(c.get(1), -1);
CHECK_EQ(c.get(3), 3);
CHECK_EQ(c.get(4), 4);
// 更新已有 key 不算新增,不触发淘汰
lc0146::LRUCache d(2);
d.put(1, 1);
d.put(2, 2);
d.put(2, 20);
CHECK_EQ(d.get(2), 20);
CHECK_EQ(d.get(1), 1);