LRU Cache Time : O(1) Space : O(capacity) 12345678910111213141516171819202122232425262728293031#include <list> list<int> lru;unordered_map<int, list<int>::iterator> lrump;unordered_map<int, int> cache;int cap;LRUCache::LRUCache(int capacity) { cap = capacity; cache.clear(); lru.clear(); lrump.clear();}int LRUCache::get(int key) { if(!cache.count(key)) return -1; set(key, cache[key]); return cache[key];}void LRUCache::set(int key, int value) { if(lrump.count(key)) lru.erase(lrump[key]); lru.push_front(key); lrump[key] = lru.begin(); cache[key] = value; while(lru.size() > cap) { int k = lru.back(); lru.pop_back(); lrump.erase(k); cache.erase(k); }}