[JAVA] Time Limit Exceeded


  • 2
    X

    Got time limit exceeded and did not know why.
    As shown in the code, I want to use Hashmap to store the key-value pairs and use Arraylist to store the keys in the LRU order.

    import java.util.*;

    public class LRUCache {

        HashMap<Integer, Integer> cacheMap; // key, value
    
        ArrayList<Integer> cacheList; // key
    
        int capacity;
    
    public LRUCache(int capacity) {
    	this.cacheMap = new HashMap<Integer, Integer>();
    	this.cacheList = new ArrayList<Integer>();
    	this.capacity = capacity;
    }
    
    public int get(int key) {
        if (this.cacheMap.containsKey(key)) {
    		this.cacheList.remove(new Integer(key));
    		this.cacheList.add(key);
    		return this.cacheMap.get(key);
    	}
    	return -1;
    }
    
    public void set(int key, int value) {
    	if (!this.cacheMap.containsKey(key)) {
    		if (this.capacity == this.cacheList.size()) {
    		    this.cacheMap.remove(this.cacheList.get(0));
    			this.cacheList.remove(0);
    		}
    		this.cacheList.add(key);
    		this.cacheMap.put(key, value);
    	} else {
    		this.cacheMap.remove(key);
    		this.cacheMap.put(key, value);
    		this.cacheList.remove(new Integer(key));
    		this.cacheList.add(key);
    	}
    }
    

    }


  • 5
    L

    The remove() method on an ArrayList takes O(n) time. You can solve LRU cache in a way such that every operation takes O(1) time.


  • -1
    H

    Do not meet 'least' condition.
    Assume the capacity is 3. Like keys input: set(2,1), set(2,1), set(1,1), set(3,1), then the cache is full.
    When set(5,1), your code replace the 2 with the 5. Obviously the key 1 should be replaced by 5, instead of 2.


  • -3
    C

    you can change ArrayList to LinkedList


  • 0
    S

    why not make a minHeap by yourself?


Log in to reply
 

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