C++ Solution using Hash Table and Binary Search Tree


  • 3
    X

    I use the hash table to search for the cache node with the key and the binary search tree to keep the order of cache nodes with frequency.
    All the operations require O(log N) complexity.

    struct CacheNode{
        int key;
        int val;
        int freq;
        CacheNode(int k, int v):freq(1), key(k), val(v){}
    };
    
    struct Compare{
        bool operator()(const CacheNode& a, const CacheNode& b){
            return a.freq < b.freq;
        }
    };
    
    class LFUCache {
    public:
        LFUCache(int capacity) {
            size = capacity;
        }
        
        int get(int key) {
            auto it = cacheMap.find(key);
            if (size == 0 || it == cacheMap.end()) return -1;
            CacheNode temp = *(it->second);
            temp.freq++;
            cacheSet.erase(it->second);
            cacheMap[key] = cacheSet.insert(temp);
            return temp.val;
        }
        
        void set(int key, int value) {
            if(size == 0) return;
            auto it = cacheMap.find(key);
            if (it == cacheMap.end()){
                if(cacheMap.size() == size){
                    cacheMap.erase((cacheSet.begin())->key);
                    cacheSet.erase(cacheSet.begin());
                }
                CacheNode temp = CacheNode(key, value);
                cacheMap[key] = cacheSet.insert(temp);
                return;
            }
            CacheNode temp = *(it->second);
            temp.freq++;
            temp.val = value;
            cacheSet.erase(it->second);
            cacheMap[key] = cacheSet.insert(temp);
        }
        
    private:
        int size;
        std::multiset<CacheNode, Compare> cacheSet;
        unordered_map<int, std::multiset<CacheNode, Compare>::iterator> cacheMap;
    };
    

  • 2
    B

    Cool name, buddy.


Log in to reply
 

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