Unordered_map + list.


  • 2
    L

    Algo: unordered map + list.
    Doesn't consider any concurrency issue or memory control.


    class LRUCache{
    public:
        LRUCache(int capacity) : cap_(capacity) {
            
        }
        
        int get(int key) {
           int ans = -1; 
    	   auto it = dic.find(key);
    	   if (it != dic.end()) {
    		   ans = it->second->second;
    		   data_.erase(it->second);
    		   data_.push_front(make_pair(key, ans));
    		   dic[key] = data_.begin();
    	   }
    	   return ans;
        }
        
        void set(int key, int value) {
    		auto it = dic.find(key);
    		if (it != dic.end()) {
    			data_.erase(it->second);
    		}
    		data_.push_front(make_pair(key, value));
    		dic[key] = data_.begin();
    		if (dic.size() > cap_) {
    			int rKey = data_.rbegin()->first;
    			data_.pop_back();
    			dic.erase(rKey);
    		}
        }
    private:
    	int cap_;
    	list< pair<int, int> > data_;
    	unordered_map<int, list< pair<int, int> >::iterator > dic;
    };

  • 0
    H

    good solution


  • 0
    C

    good learning about the iterator!


  • 0
    W

    I'm sorry, It may TLE...


  • 0
    L
    This post is deleted!

Log in to reply
 

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