C++ 138 ms - O(1) with two arrays


  • 0
    V

    I used fixed-size arrays and did not free the memory to see how fast can it get... One array is to look-up values, another array holds lists for frequencies 1..n. When you bump up the frequency, the element is moved to the front of the list for frequency + 1.

    class LFUCache {
        struct LFUInfo
        {
            int frequency = 1;
            int value;
            list<int>::iterator l_it;
            LFUInfo(int value, const list<int>::iterator& it) : value(value), l_it(it) {}
        };
    
        list<int> *m_l[29] = {};
        LFUInfo* m[2700] = {};
        int cap, min_frequency = 1, size = 0;
    
        void bumpFrequency(list<int>::iterator& it, int frequency)
        {
            if (m_l[frequency + 1] == NULL) m_l[frequency + 1] = new list<int>();
            m_l[frequency + 1]->splice(m_l[frequency + 1]->begin(), *m_l[frequency], it);
            if (frequency == min_frequency && m_l[frequency]->empty()) ++min_frequency;
        }
        
    public:
        LFUCache(int capacity) : cap(capacity) {m_l[1] = new list<int>();}
    
        int get(int key) 
        {
            auto value = -1;        
            if (m[key] == NULL) return -1;
            bumpFrequency(m[key]->l_it, m[key]->frequency++);
            return m[key]->value;
        }
        
        void put(int key, int value) 
        {
            if (cap == 0) return;
            if (m[key] != NULL)
            {
                m[key]->value = value;
                bumpFrequency(m[key]->l_it, m[key]->frequency++);
            }
            else
            {
                if (size == cap)
                {
                    m[m_l[min_frequency]->back()] = NULL;
                    m_l[min_frequency]->pop_back();
                }
                else ++size;
                
                min_frequency = 1;
                m_l[1]->push_front(key);
                m[key] = new LFUInfo(value, m_l[1]->begin());
            }
        }
    };
    

Log in to reply
 

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