Rewritten the code with detailed explanation


  • 0
    L

    I've rewritten the code and remove the unnecessary variables by using map for frequency instead of unordered_map.
    The detailed data structure is drawn below:

    • cache: hash map to use key to find value and frequency
    • itor: hash map to use key to find iterator of the element in freqs map
    • freqs: ordered map to record the frequency of each element. Elements with same frequency are put in the same list

    0_1484001470071_LFU.png

    class LFUCache {
    public:
        LFUCache(int capacity):ways(capacity) {
            
        }
        
        int get(int key) {
            if (cache.find(key) == cache.end()) return -1;
            // update frequency
            int freq = cache[key].second;
            auto it = itor[key];
            freqs[freq].erase(it);
            if (freqs[freq].empty()) freqs.erase(freq);
            ++freq;
            freqs[freq].push_back(key);
            itor[key] = --freqs[freq].end();
            cache[key].second = freq;
            
            return cache[key].first;
        }
        
        void put(int key, int value) {
            if (ways <=0 ) return;
            if(get(key) != -1) {
                cache[key].first=value;
                return;
            }
            
            if (cache.size() >= ways) {
                int rmkey = freqs.begin()->second.front();
                freqs.begin()->second.pop_front();
                if (freqs.begin()->second.empty()) freqs.erase(freqs.begin());
                cache.erase(rmkey);
                itor.erase(rmkey);
            }
            
            cache[key]=make_pair(value, 1);
            freqs[1].push_back(key);
            itor[key]=--freqs[1].end();
        }
        
    private:
        unordered_map<int, pair<int, int> > cache;
        unordered_map<int, list<int>::iterator> itor;
        map<int, list<int> > freqs;
        int ways;
    };
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

Log in to reply
 

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