C++ 153ms 60lines Solution with hashmap, beats 99.46%.


  • 0
    M
    struct MxNode{
        int key,val,cnt;
        MxNode *prev,*next;
        MxNode(int k,int v):key(k),cnt(0),val(v),prev(nullptr),next(nullptr){}
    };
    
    class LFUCache {
    private:
        int rem;
        unordered_map<int,MxNode*> pos;
        vector<MxNode*> last;
        void update(MxNode *node){
            for(int i=node->cnt;i<last.size()&&last[i]==node;++i) last[i]=node->prev;
            if(node->prev) node->prev->next=node->next;
            if(node->next) node->next->prev=node->prev;
            if(++node->cnt==last.size()) last.push_back(last[node->cnt-1]);
            node->next=last[node->cnt]->next;
            node->prev=last[node->cnt];
            if(node->next) node->next->prev=node;
            node->prev->next=node;
            for(int i=node->cnt;i<last.size()&&last[i]==node->prev;++i) last[i]=node;
        }
        void del(MxNode *node){
            node->prev->next=node->next;
            if(node->next) node->next->prev=node->prev;
            for(int i=node->cnt;i<last.size()&&last[i]==node;++i) last[i]=node->prev;
            pos.erase(node->key);
            delete node;
        }
    public:
        LFUCache(int capacity):rem(capacity),last(0){
            last.emplace_back(new MxNode(-1,-1));
            pos.clear();
        }
        
        int get(int key) {
            if(pos.find(key)==pos.end()) return -1;
            MxNode *node=pos[key];
            update(node);
            return node->val;
        }
        
        void set(int key, int value) {
            if(rem==0&&pos.size()==0) return;
            if(pos.find(key)==pos.end()){
                MxNode *node=pos[key]=new MxNode(key,value);
                update(node);
                if(rem) --rem;
                else if(last[0]->next==node) del(node->next);
                else del(last[0]->next);
            }else{
                MxNode *node=pos[key];
                node->val=value;
                update(node);
            }
        }
    };
    

    I think it can do better if we use a better struct to replace the vector "last", so that we can update the array last without loop.


  • 0
    M
    This post is deleted!

Log in to reply
 

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