Accept C++ solution (221ms)


  • 0
    X
    class LRUCache{
    
    public:
        long long timestamp;
        int size;
        int capacity;
        map<long long, int> tk;
        map<int, long long> kt;
        map<int, int> kv;
        
        LRUCache(int capacity) {
            size = 0;
            this->capacity = capacity;
        }
        
        int get(int key) {
            timestamp ++;
            int ret = -1;
            if (kv.find(key) != kv.end())
            {
                ret = kv[key];
                tk.erase(tk.find(kt.find(key)->second));
                kt[key] = timestamp;
                tk[timestamp] = key;
            }
            return ret;
        }
        
        void set(int key, int value) {
            timestamp ++;
            if (kv.find(key) != kv.end())
            {
                kv[key] = value;
                tk.erase(tk.find(kt.find(key)->second));
                kt[key] = timestamp;
                tk[timestamp] = key;
            } 
            else if (size < capacity)
            {
                size ++;
                kv[key] = value;
                kt[key] = timestamp;
                tk[timestamp] = key;
            }
            else
            {
                long long minTime = tk.begin()->first;
                int minKey = tk.begin()->second;
                kv.erase(kv.find(minKey));
                kv[key] = value;
                kt.erase(kt.find(minKey));
                tk.erase(tk.find(minTime));
                kt[key] = timestamp;
                tk[timestamp] = key;
            }
        }
    };

Log in to reply
 

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