C++ O(1) solution using 1 linked list and 2 hash tables


  • 0
    B
    class LFUCache {
    public:
        LFUCache(int capacity) {
            //mTbl.size() always equals to mList.size()
            mCapacity = capacity;
        }
        
        int get(int key) {
            //find key in table.
            MyTbl::iterator it = mTbl.find(key);
            if (it != mTbl.end()) {                             //if found.
                int value = it->second->val;                    //get the value to return;
                it->second = getNewListIter(it->second);        //update tables and reorder list.
                return value;
            } else {                                            //return -1, if not found.
                return -1;
            }
        }
        
        void set(int key, int value) {
            if (mCapacity == 0) {
                return;
            }
            MyTbl::iterator it = mTbl.find(key);
            if (it == mTbl.end()) {                 //not exist;
                if (mList.size() == mCapacity) {    //cache's full, pop the front element.
                    //erase the first element in from mTbl;
                    int key_to_erase = mList.front().key; 
                    mTbl.erase(key_to_erase);
                    int freq = mList.front().freq;
                    MyFreqTbl::iterator freq_it = mFreqTbl.find(freq);
                    if (freq_it != mFreqTbl.end() && freq_it->second == mList.begin()) {
                        if (freq_it->second == mList.begin() || (--freq_it->second)->freq != freq) {
                            mFreqTbl.erase(freq_it);
                        }
                    }
                    mList.pop_front();  //list.size() - 1;
                }
                MyListItem item_to_insert;
                item_to_insert.key = key;
                item_to_insert.val = value;
                item_to_insert.freq = 1;
                //find pos to insert
                MyFreqTbl::iterator insert_it = mFreqTbl.find(1);   //new item's freq is 1.
                if (insert_it == mFreqTbl.end()) {                  //no such freq, insert front
                    mList.push_front(item_to_insert);
                    MyList::iterator list_it = mList.begin();
                    mFreqTbl.insert(make_pair(1, list_it));
                    mTbl.insert(make_pair(key, list_it));
                } else {
                    ++insert_it->second;
                    MyList::iterator list_it = mList.insert(insert_it->second, item_to_insert);
                    insert_it->second = list_it;
                    mTbl.insert(make_pair(key, list_it));
                }
            } else {    //if in list. only change pos as get().
                it->second = getNewListIter(it->second);
                //update value;
                it->second->val = value;
            }
        }
    private:
        struct MyListItem {
            int key;
            int val;
            int freq;
        };
        typedef list<MyListItem> MyList;
        typedef unordered_map<int, MyList::iterator> MyTbl;
        typedef unordered_map<int, MyList::iterator> MyFreqTbl;
        
        //this function called when operating list_it in mTlb
        MyList::iterator getNewListIter(MyList::iterator list_it) {
            //get freq and value, and erase from list
            MyList::iterator ret_it = list_it;
            MyListItem item = *list_it;
            //insert then remove;
            ++item.freq;    //freq >= 2;
            MyFreqTbl::iterator freq_it = mFreqTbl.find(item.freq);
            if (freq_it != mFreqTbl.end()) {    //find position to insert
                ++freq_it->second;
                ret_it = mList.insert(freq_it->second, item);
                freq_it->second = ret_it;
                freq_it = mFreqTbl.find(list_it->freq);
            } else {    //iterator not found.
                //find list_it->freq, which is must in the table.
                freq_it = mFreqTbl.find(list_it->freq);
                if (freq_it != mFreqTbl.end()) {
                    ret_it = freq_it->second;
                    ret_it = mList.insert(++ret_it, item);
                    mFreqTbl.insert(make_pair(item.freq, ret_it));
                }
            }
            //if list_it is the iterator in mFreqTbl
            if (freq_it->second == list_it) {
                if (freq_it->second == mList.begin() || (--freq_it->second)->freq != list_it->freq) {
                    mFreqTbl.erase(freq_it);
                }
            }
            mList.erase(list_it);
            return ret_it;
        }
        
        MyList mList;               //least freqQ of keys;
        MyTbl mTbl;                 //hashtable<key, list_it(to_find_value)>
        MyTbl mFreqTbl;             //hashtable<freq, list_it(to insert)>
        
        int mCapacity;
    };
    

Log in to reply
 

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