Why Time Exceed Java


  • 1
    F

    I didn't create my own nodes, because java LinkedList is already a double linkedList. I cast all the key to Object in order to use the double LinkedList feature in Java.

    But it still show time exceed error, anyone can figure out why this happened? below is the code

    public class LRUCache {
        private HashMap<Integer, Object> map = new HashMap<Integer, Object>();
        private LinkedList<Object> list = new LinkedList<Object>();
        private int size = 0;
        private int capacity;
        
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if (map.containsKey((Object)key)) {
                list.remove((Object)key);
                list.addFirst((Object)key);
                return (int)map.get((Object)key);
            } else {
                return -1;
            }
            
        }
        
        public void set(int key, int value) {
            //key not exist
            if (!map.containsKey(key)) {
                if (size < this.capacity) {     //cache is not full
                    list.addFirst((Object)key);
                    map.put(key, (Object)value);
                    size++;
                } else {   //cache is full
                    Object lastKey = list.getLast();
                    list.removeLast();
                    map.remove(lastKey);
                    list.addFirst((Object)key);
                    map.put(key, (Object)value);
                }
            } else {    //contains the key
                list.remove((Object)key);
                list.addFirst((Object)key);
                map.put(key,(Object)value);
            }
        }
    }

  • 4
    Y

    My solution is almost identical, and I also got TLE.
    I think it is because "list.remove((Object)key);" is linear .


  • 0
    N

    yes, it is. I wrote in C++ and timeout due to this.
    just add another hash-table to quick find the node of key in list. make it O(1)


Log in to reply
 

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