Question about LRUCache


  • 0
    A

    public class LRUCache {

    private LinkedList<Integer> cache=new LinkedList<Integer>();
    private int capacity;
    private HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
    
    public LRUCache(int capacity) {
        this.capacity=capacity;
    }
    
    public int get(int key) {
        if(map.containsKey(key))
        {
            int val=map.get(key);
            cache.removeFirstOccurrence(key);
            cache.addFirst(key);
            return val;
        }else
            return -1;
    }
    
    public void set(int key, int value) {
        if(map.containsKey(key))
        {
            cache.removeFirstOccurrence(key);
            cache.addFirst(key);
        }else
        {
            if(cache.size()==capacity)
            {
                int lastKey=cache.removeLast();
                map.remove(lastKey);
            }
            cache.push(key);
            map.put(key,value);
        }
    }
    

    }

    This is my source code about LRUCache. LinkedList is used to maintain the order of keySet because it is fast when insert or remove the elements in the list. HashMap is used to search the value because the time complexity is O(1). However, my code is time limited exceeded. So can anyone tell me why? Thanks a lot!


  • 0
    Z

    my code is similar and is time limited exceeded。I guess the reason is linkedlist remove is O(N),but leetcode is ordered to be O(1),but i don't know any better collection,is anyone can ac with java?what kind of collection is used?thansk a lot


  • 0
    Z

    I also tried LinkedHashMap,TLE


  • 0
    J

    the problem is cache.size() in some compiler is O(n), try change your cache.size() to use map.size().
    this solves the problem.
    Sorry, didn't notice it's Java, what I said is for C++ :-)


Log in to reply
 

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