C++ solution using unordered map and queue, easy to understand


  • 1
    N
    class LRUCache{
    public:
    
    LRUCache(int capacity) { //constructor
        _capacity = capacity;
    }
    
    int get(int key) {
        if(map2val.count(key)>0){
            q.push(key);
            map2count[key]++;
            return map2val[key];
        }
        else
            return -1;
    }
    
    void set(int key, int value) {
        if(map2val.count(key)>0){ //set the key's value
            map2val[key] = value;
            q.push(key);
            map2count[key]++;
        }
        else{ //insert new key
            while(map2count.size() > _capacity-1){ //must left a place for a new key
                int LRUkey = q.front();
                q.pop(); //pop the least recently used key
                map2count[LRUkey]--;
                if(map2count[LRUkey]==0){
                    map2count.erase(LRUkey);
                    map2val.erase(LRUkey);
                }
            }
            q.push(key); //push the new key
            map2val[key] = value; //set new key's value
            map2count[key] = 1; //key appears first time, count is 1
        }
    }  
    
    private:
        int _capacity;
        queue<int> q; //store the recently used keys, FIFO structure
        unordered_map<int,int> map2val; //map the key to its value
        unordered_map<int,int> map2count; //map the key to its count, +1 if the key is used
    };

  • 0
    A

    how do you know the first (front) element in the queue, is the least recently used?


  • 0
    N

    Every time you use the key, either get or set, you push the key to the back of the queue. Thus, the back element is the recently used key(you just push it), while the front element is the least recently used. The keys in the queue are in the same order of the time you use the key.


  • 0
    V

    if i keep setting the value with same key , or keeping getting value with same key, the size of the queue would keep growing without limit.


Log in to reply
 

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