Why my solution exceeds the time limit?


  • 1
    A

    is it because the indoexof operation is O(n)?

    public class LRUCache {

    HashMap<Integer, Integer> map;
    LinkedList<Integer> qu;
    int size = 0;
    public LRUCache(int capacity) {
        map = new HashMap<Integer, Integer>();
        qu = new LinkedList<Integer>();
        size = capacity;
    }
    
    public int get(int key) {
        int value = -1;
        int index = -1;
    	if (map.containsKey(key))
        {
    		index = qu.indexOf(key);
        	qu.remove(index);
        	qu.add(key);
        	value =  map.get(key);
        }
    
    	return value;
    }
    
    public void set(int key, int value) {
    	int topKey = -1;
        int index = -1;
    	if (map.containsKey(key))
    	{
    		map.put(key, value);
    		index = qu.indexOf(key);
    		qu.remove(index);
    	}
    	else
    	{
    		if (size <= map.size())
            {
    			// we need to remvoe elements to make room
            	topKey = qu.remove(0);
            	map.remove(topKey);
            }
    		
    		map.put(key, value);
    	}
    	qu.add(key);
           	
    }
    

    }


  • 1
    M

    You are on the right path, and are almost certainly right about the indexOf problem, but O(n) occurs in other places as well. If you make the Linked list yourself (especially a doubly linked list), you can make the map an < Integer, Node > map, which lets you have O(1) accessing, removal, and insertion, while based on how Java implements the LinkedList class, it might have O(n) for accessing and removal, as well as indexOf.


  • 0
    A

    indeed, the doubly linked list solved the problem. thanks


Log in to reply
 

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