请你设计并实现一个满足 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) 的平均时间复杂度运行
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: unordered_map<int, int> mp; unordered_map<int, int> cnt; queue<int> q; int sz; int capacity; LRUCache(int capacity) { this->capacity = capacity; sz = 0; }
int get(int key) { if (cnt[key]) { q.push(key); cnt[key]++; return mp[key]; } return -1; }
void put(int key, int value) { if (sz < capacity) { if (cnt[key]) { cnt[key]++; mp[key] = value; } else { cnt[key]++; mp[key] = value; sz++; } q.push(key); } else { if (!cnt[key]) { while (q.size()) { int k = q.front(); q.pop(); cnt[k]--; if (!cnt[k]) { mp.erase(k); break; } } } mp[key] = value; cnt[key]++; q.push(key); } } };
|