c++ 188ms


  • 0
    S
    class LFUCache {
    public:
        LFUCache(int capacity) : _capacity(capacity)
        {
    
        }
    
        int get(int key)
        {
            if(_valueMap.find(key) == _valueMap.end())
                return -1;
    
            rearrangeCache(key);
            return _valueMap[key].first;
        }
    
        void set(int key, int value)
        {
            if(_capacity < 1)
                return;
                
            auto vit = _valueMap.find(key);
            if(vit == _valueMap.end())
            {
                evictCache();
    
                auto lit = _countList.begin();
                auto mit = _countMap.find(1);
                if(mit != _countMap.end())
                {
                    lit = mit->second;
                    ++lit;
                }
    
                auto nit = _countList.insert(lit, make_pair(key, 1));
                _countMap[1] = nit;
                _valueMap[key] = make_pair(value, nit);
    
                return;
            }
    
            rearrangeCache(key);
            vit->second.first = value;
        }
    
    private:
        void evictCache()
        {
            if(_valueMap.size() <  _capacity)
                return;
    
            auto lit = _countList.begin();
            if(_countMap[lit->second] == lit)
                _countMap.erase(lit->second);
            _valueMap.erase(lit->first);
            _countList.erase(lit);
        }
    
        void rearrangeCache(int key)
        {
            auto it = _valueMap.find(key);
            auto lit = it->second.second;
            int count = lit->second;
            if(_countMap[count] == lit)
            {
                auto pit = lit;
                if(lit == _countList.begin() || (--pit)->second != lit->second)
                    _countMap.erase(count);
                else
                    _countMap[count] = pit;
            }
    
            ++count;
            lit = _countList.erase(lit);
            auto mit = _countMap.end();
            if((mit = _countMap.find(count)) != _countMap.end() ||
               (mit = _countMap.find(count-1)) != _countMap.end())
            {
                lit = mit->second;
                ++lit;
            }
            it->second.second = _countList.insert(lit, make_pair(key, count));
            _countMap[count] = it->second.second;
        }
    
        const int _capacity;
        list<pair<int, int>> _countList;
        unordered_map<int, list<pair<int, int>>::iterator> _countMap;
        unordered_map<int, pair<int, list<pair<int, int>>::iterator>> _valueMap;
    };
    

Log in to reply
 

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