Why is my solution TLE?


  • 0
    C
    class LRUCache{
    public:
    LRUCache(int capacity) {
        Cap = capacity;
    }
    
    int get(int key) {
        if(mp.find(key)!=mp.end()){
            int x = touch(key);
            cout<<x<<endl;
            return mp[key];
        }
    	else {return -1;}
    }
    
    void set(int key, int value) {
    	int x = touch(key);
    	cout<<x<<endl;
        if(mp.find(key)!=mp.end()){
            mp[key] = value;
        }
        else{
            if(vst.size()<Cap){
                mp[key] = value;
            }
            else{
                mp.erase(x);
                mp[key] = value;
            }
        }
    }
    private:
    int Cap;
    unordered_set<int> vst;
    unordered_map<int,int> mp;
    int touch(int key){
        if(vst.size()<Cap){
    		if(vst.find(key)!=vst.end()) vst.erase(key);
    		vst.insert(key);
        }
        else{
            if(vst.find(key)==vst.end()){
    			int toReplace = *vst.begin();
    			vst.erase(vst.begin());
    			vst.insert(key);
    			return toReplace;
            }
            else{
    			vst.erase(key);
    			vst.insert(key);
            }
        }
        return 0;
    }
    
    };

Log in to reply
 

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