C++, 89ms


  • 0
    C
    #include <list>
    #include <unordered_map>
    
    using namespace std;
    
    class LFUCache {
    public:
        using TKey = int;
        using TValue = int;
    
    private:
        using TLruList = std::list<TKey>;
    
        struct TFreqListItem {
            TFreqListItem(size_t freq = 1)
                : Freq(freq)
            {
            }
    
            size_t Freq;
            TLruList LruList;
        };
    
        using TFreqList = std::list<TFreqListItem>;
    
        struct TLookupItem {
            TValue Value;
            TFreqList::iterator FreqIt;
            TLruList::iterator LruIt;
        };
    
        using TMap = unordered_map<TKey, TLookupItem>;
    
        TFreqList FreqList;
        TMap Map;
        size_t Capacity;
    
    public:
        LFUCache(int capacity)
            : Capacity(capacity)
        {
        }
    
        int get(const TKey key) {
            if (!Capacity) {
                return -1;
            }
    
            auto it = Map.find(key);
            if (it == Map.end()) {
                return -1;
            }
    
            Touch(it);
            return it->second.Value;
        }
    
        void put(const TKey key, const TValue value) {
            if (!Capacity) {
                return;
            }
    
            {
                auto mapIt = Map.find(key);
                if (mapIt != Map.end()) {
                    mapIt->second.Value = value;
                    Touch(mapIt);
                    return;
                }
            }
    
            if (Map.size() == Capacity) {
                EraseWorst();
            }
    
            if (FreqList.empty() || FreqList.begin()->Freq != 1) {
                FreqList.emplace_front();
            }
    
            const auto freqIt = FreqList.begin();
            auto& lru = freqIt->LruList;
            const auto lruIt = lru.insert(lru.end(), key);
            Map.emplace(key, TLookupItem{value, freqIt, lruIt});
        }
    
    private:
        void Touch(TLookupItem& item) {
            const size_t nextFreq = item.FreqIt->Freq + 1;
    
            auto tgtFreqIt = item.FreqIt;
            ++tgtFreqIt;
            if (tgtFreqIt == FreqList.end() || tgtFreqIt->Freq > nextFreq) {
                tgtFreqIt = FreqList.emplace(tgtFreqIt, nextFreq);
            }
    
            auto& oldLru = item.FreqIt->LruList;
            auto& newLru = tgtFreqIt->LruList;
    
            newLru.splice(newLru.end(), oldLru, item.LruIt);
            // item.LruIt is valid
    
            if (oldLru.empty()) {
                FreqList.erase(item.FreqIt);
            }
    
            item.FreqIt = tgtFreqIt;
        }
    
        void Touch(TMap::iterator it) {
            Touch(it->second);
        }
    
        void EraseWorst() {
            auto& lru = FreqList.begin()->LruList;
            const TKey key = *lru.begin();
            lru.erase(lru.begin());
            if (lru.empty()) {
                FreqList.erase(FreqList.begin());
            }
            Map.erase(key);
        }
    };
    

Log in to reply
 

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