C++ solution, 82 ms


  • 0
    X
    class LRUCache
    {
    	public:
    		struct Index
    		{
    			int key;
    			Index* next;
    			Index* prev;
    			Index(int k): key(k), next(NULL), prev(NULL)
    			{}
    		};
    
    		struct Value
    		{
    			int val;
    			Index* index;
    			Value(int v, Index* i): val(v), index(i)
    			{}
    			Value()
    			{
    				val = 0;
    				index = NULL;
    			}
    		};
    
    		LRUCache(int capacity)
    		{
    			this->capacity = capacity;
    			indexHead = new Index(0);
    			indexTail = new Index(0);
    			indexHead->next = indexTail;
    			indexTail->prev = indexHead;
    		}
    
    		~LRUCache()
    		{
    			delete indexHead;
    			delete indexTail;
    		}
    
    		int get(int key)
    		{
    			if(m.end() == m.find(key))
    				return -1;
    			else
    			{
    				Value val = m[key];
    				Index* index = val.index;
    				/*index->prev->next = index->next;
    				index->next->prev = index->prev;
    				index->next = indexHead->next;
    				indexHead->next->prev = index;
    				index->prev = indexHead;
    				indexHead->next = index;*/
    				updateIndex(index);
    				return val.val;
    			}
    		}
    
    		void set(int key, int value)
    		{
    			if(m.end() != m.find(key))
    			{
    				Value val = m[key];
    				val.val = value;
    				m[key] = val;
    				Index* index = val.index;
    				updateIndex(index);
    			}
    			else
    			{
    				if(m.size() == capacity)
    				{
    					Index* index = indexTail->prev;
    					index->prev->next = indexTail;
    					indexTail->prev = index->prev;
    					m.erase(index->key);
    					delete index;
    				}
    
    				Index* index = new Index(key);
    				Value val(value, index);
    				m[key] = val;
    				index->next = indexHead->next;
    				indexHead->next->prev = index;
    				indexHead->next = index;
    				index->prev = indexHead;
    			}
    		}
    
    		void updateIndex(Index* &index)
    		{
    			index->next->prev = index->prev;
    			index->prev->next = index->next;
    			index->next = indexHead->next;
    			indexHead->next->prev = index;
    			index->prev = indexHead;
    			indexHead->next = index;
    		}
    	private:
    		unordered_map<int, Value> m;
    		int capacity;
    		Index* indexHead;
    		Index* indexTail;
    };

Log in to reply
 

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