C++11 code 62ms - Hash table + List


  • 0
    S
    class LRUCache{
    public:
        // in list, key is again stored, to recognize the key while removing the least recently used (last) element from list
        list<pair<int, int>> l;
        unordered_map<int, list<pair<int, int>>::iterator> m;
        int capacity;
        
        LRUCache(int capacity) {
            this->capacity = capacity;
        }
        
        int get(int key) {
            auto it = m.find(key);
            if(it != m.end()) {
                auto lit = it->second;
                l.splice(l.begin(), l, lit);
                return lit->second;
            }
            else return -1;
        }
        
        void set(int key, int value) {
            auto it = m.find(key);
            if(it != m.end()) {
                auto lit = it->second;
                lit->second = value;
                l.splice(l.begin(), l, lit);
            }
            else {
                // key doesnt exist in cache yet
                if(l.size() == capacity) {
                    int lru_key = l.back().first;
                    m.erase(lru_key);
                    l.pop_back();
                }
                l.push_front(make_pair(key,value));
                m[key] = l.begin();
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.