C++ second level list + unordered_map O(1) solution


  • 0
    A

    Presuming we treat unordered_map as O(1) access time.

    23 / 23 test cases passed
    Status: Accepted
    Runtime: 182 ms

    class LFUCache {
    protected:
        list<pair<uint, list<pair<int, uint>>>> lst;
        unordered_map<int, pair<list<pair<uint, list<pair<int, uint>>>>::iterator, list<pair<int, uint>>::iterator>> map;
        uint siz;
    public:
        LFUCache(int capacity) {
            siz = capacity;
        }
        
        int get(int key) {
            auto it = map.find(key);
            if (it == map.end()) return -1;
            uint val = it->second.second->second;
            refresh(it);
            return val;
        }
        
        void set(int key, int value) {
            auto it = map.find(key);
            if (it != map.end()) {
                it->second.second->second = value;
                refresh(it);
                return;
            }
            list<pair<uint, list<pair<int, uint>>>>::iterator it1;
            list<pair<int, uint>>::iterator it2;
            if (siz) siz--;
            else if (!lst.size()) return;
            else {
                auto it2 = lst.begin()->second.begin();
                map.erase(it2->first);
                lst.begin()->second.erase(it2);
            }
            if (!lst.size() || lst.front().first) it1 = lst.insert(lst.begin(), make_pair(0u, list<pair<int, uint>>()));
            else it1 = lst.begin();
            it2 = it1->second.insert(it1->second.end(), make_pair(key, (uint)value));
            map[key] = make_pair(it1, it2);
        }
        
        void refresh(unordered_map<int, pair<list<pair<uint, list<pair<int, uint>>>>::iterator, list<pair<int, uint>>::iterator>>::iterator it) {
            auto it1 = it->second.first;
            auto it2 = it->second.second;
            uint freq = it1->first, val = it2->second;
            if (it1->second.size() != 1) {
                it1->second.erase(it2);
                if (next(it1) == lst.end() || next(it1)->first != freq + 1) it1 = lst.insert(next(it1), make_pair(freq + 1, list<pair<int, uint>>()));
                else it1 = next(it1);
                it2 = it1->second.insert(it1->second.end(), make_pair(it->first, val));
                it->second = make_pair(it1, it2);
            } else if (next(it1) == lst.end() || next(it1)->first != freq + 1) it1->first++;
            else {
                it1 = lst.erase(it1);
                it2 = it1->second.insert(it1->second.end(), make_pair(it->first, val));
                it->second = make_pair(it1, it2);
            }
        }
    };
    

Log in to reply
 

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