C++ Solution with unordered_map and priority_queue, 189ms beats 84.41%


  • 0
    J

    I use a unordered_map to track the correct key value pair and corresponding to its counter and newest timer. And use a priority_queue to lazy store the current data, the priority_queue is sorted by its frequency and time.

    class LFUCache {
    private:
        struct Node {
            int key, val;
            int freq;
            long time;
            Node(int k, int v, int f, long t) : key(k), val(v), freq(f), time(t) {}
            Node() : key(0), val(0), freq(0), time(0) {}
            friend bool operator<(const Node& a, const Node& b) {
                if(a.freq == b.freq) return a.time > b.time;
                return a.freq > b.freq;
            }
        };
        // key -> Node map
        unordered_map<int, Node> _umap;
        // sorted by freq and time
        priority_queue<Node> _pq;
        int _cap;
        static long curTime;
        
    public:
        LFUCache(int capacity) {
            _cap = capacity;
        }
        
        int get(int key) {
            if(_cap <= 0) return -1;
            if(_umap.find(key) == _umap.end()) return -1;
            _umap[key].freq ++;
            _umap[key].time = curTime ++;
            return _umap[key].val;
         }
        
        void set(int key, int value) {
            if(_cap <= 0) return; 
            if(_umap.find(key) != _umap.end()) {
                _umap[key].freq ++;
                _umap[key].time = curTime ++;
                _umap[key].val = value;
            }
            else {
                clrExpire();
                _umap[key] = Node(key, value, 1, curTime);
                _pq.push(Node(key, value, 1, curTime ++));
            }
        }
        
        void clrExpire() {
            while(!_pq.empty() && _pq.size() >= _cap) {
                Node tmp = _pq.top();
                _pq.pop();
                // lazy update, if the record in the priority_queue is not the same as 
                // the newest record in the unordered_map, then update it and push back
                // to the priority_queue
                if(_umap[tmp.key].freq != tmp.freq || _umap[tmp.key].time != tmp.time) {
                    _pq.push(_umap[tmp.key]);
                }
                else _umap.erase(_umap.find(tmp.key));
            }
            
        }
    };
    
    long LFUCache::curTime = 0;
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.set(key,value);
     */
    

Log in to reply
 

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