LRU cache . Unordered map, Time limit exceeded


  • 0
    N
    class LRUCache{
    private:
            int capacity;
            
            unordered_map <int, int> mymap;
            pair<int, int> newpair;
            list<int> replace;                                          //replace list record the queue of the key,everytime 
                                                                        //updates the cache,the key is set as the first elements of the queue                                                                      
    public:
        LRUCache(int capacity) {
            this->capacity=capacity;
        }
        
        int get(int key) {
            if(mymap.count(key)){
                replace.remove(key); 
                replace.push_front(key);                            //read cache, if key is found, push the key to the front
                return mymap.at(key);
            }
            else 
                return -1;
           
        }
        
        void set(int key, int value) {
            if(get(key)>0){
                mymap.at(key)=value;                                //key is found. set new value
            }
            else if (mymap.size()<capacity){                        //cache not full  , insert new pair
                
                newpair=make_pair(key,value);
                replace.push_front(key);
                mymap.insert(newpair);
            }
            else{                                               //cache full, 
                find2replace();
                newpair=make_pair(key,value);                   //insert new pair
                replace.push_front(key);
                mymap.insert(newpair);
            }
            
            return;
        }
        
        
        void find2replace(){                                         //pop the LRU key, erase the pair
            int victim=replace.back();
            replace.pop_back();
            mymap.erase(victim);
            return;
        }
    };

  • 0
    C

    replace.remove(key); complexity is : O(n)


Log in to reply
 

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