Is set operation considered as reference? I could not find the reason my solution is wrong.


  • 0
    Y

    class LRUCache{
    private:
    list < pair < int, int > > m_data;
    unordered_map < int, list < pair < int, int > >::iterator > index;
    int m_capacity;

    public:
    LRUCache(int capacity) : m_data(), index(), m_capacity(capacity)
    {
    }

    int get(int key) {
    	if (index.find(key) != index.end())
    	{
    		list < pair < int, int > >::iterator itr = index[key]; 
    		int val = (*(index[key])).second;
    		m_data.erase(itr);
    		m_data.push_front(make_pair(key, val));
    		index[key] = m_data.begin();
    		return val;
    	}
    	else
    	{
    		return -1;
    	}
    }
    
    void set(int key, int value) 
    {
    	if (index.find(key) != index.end())
    	{
    		m_data.erase(index[key]);
    		index.erase(key);
    		m_data.push_front(make_pair(key, value));
    		index[key] = m_data.begin();
    	}
    
    	if (index.size() < m_capacity)
    	{
    		m_data.push_front(make_pair(key, value));
    		index[key] = m_data.begin();
    	}
    	else
    	{
    		int k = m_data.back().first;
    		m_data.pop_back();
    		index.erase(k);
    		m_data.push_front(make_pair(key, value));
    		index[key] = m_data.begin();
    	}
    }
    

    };


  • 0
    S

    In your set function, there are two if blocks. You should return from the function at the end of the first block (inside the block). Otherwise you will be pushing two pairs into the list.


  • 0
    Y

    Thanks, spundun.


Log in to reply
 

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