C++ O(1) solution using Hash Table and List


  • 0
    T
    class LFUCache {
        map<int, list<pair<int,int>>> arr;   //Index: frequency, value:  store key and value pairs
        unordered_map<int, pair<int, list<pair<int,int>>::iterator> > hash; // stores frq and (key, value) for O(1) 
        int cap ;
        int cnt ;
    public:
        LFUCache(int capacity) {
            cap = capacity;
            cnt = 0;
        }
        
        int get(int key) {
            if(hash.count(key) == 0) return -1;
            auto it = hash[key];
            auto pos = it.second;
            int val = pos->second;
            int frq = it.first;
            
            arr[frq].erase(pos);
            if(arr[frq].size() == 0) {
                arr.erase(arr.find(frq));
            }
            
            arr[frq+1].push_back(make_pair(key,val));
            pos = arr[frq+1].end();
            pos--;
            hash[key].second = pos;
            hash[key].first++;
            
            return val;
        }
        
        void set(int key, int value) {
            if(cap == 0) return ;
            if(hash.count(key) > 0){
                get(key);
                hash[key].second->second = value;
            }else{
                if(cnt == cap){
                    auto st = arr.begin();
                    int toRemove = st->second.begin()->first;
                    hash.erase(toRemove);
                    st->second.pop_front();
                    if(st->second.size() == 0){
                        arr.erase(st);
                    }
                }else{
                    cnt++;
                }
                
                arr[1].push_back(make_pair(key,value));
                auto it = arr[1].end();
                it--;
                hash[key].second = it;
                hash[key].first = 1;
            }
        }
    };
    

  • 0
    J

    Find of Map has complexity of logarithmic in the size of the container.


  • 0
    A
    This post is deleted!

Log in to reply
 

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