LRU缓存是面试中很容易考到的一个知识点,除了要对其原理熟悉之外,也要掌握其简单实现。通过采用两个hash map + list的数据结构,可以在O(1)的时间复杂度下实现get和put操作。
class LRUCache {
private:
int size;
list<int> lru; //key
unordered_map<int, list<int>::iterator> map; //key, iterator
unordered_map<int, int> kv; //key, value
void update(int key) {
if (kv.find(key) != kv.end())
lru.erase(map[key]);
lru.push_front(key);
map[key] = lru.begin();
}
void evict() {
map.erase(lru.back());
kv.erase(lru.back());
lru.pop_back();
}
public:
LRUCache(int capacity) {
size = capacity;
}
int get(int key) {
if (kv.find(key) == kv.end())
return -1;
update(key);
return kv[key];
}
void put(int key, int value) {
if (kv.size() == size && kv.find(key) == kv.end())
evict();
update(key);
kv[key] = value;
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/