[Java] Why time limit exceeded? Help!


  • 0
    J
    public class LRUCache {
    int capacity;
    HashMap<Integer, Integer> valueTable;
    List q;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        valueTable = new HashMap<>();
        q = new List(capacity);
    }
    
    public int get(int key) {
        if (!valueTable.containsKey(key)) {
            System.out.println("-1");
            return -1;
        }
        else {
            if (valueTable.get(key)!=-1) set(key, valueTable.get(key));
        }
        System.out.println(valueTable.get(key));
        return valueTable.get(key);
    }
    
    public void set(int key, int value) {
        Node toBeDeleted = q.add(key);
        if (toBeDeleted!=null) {
            valueTable.put(toBeDeleted.val, -1);
            valueTable.put(key, value);
        }
        else {
            valueTable.put(key, value);
        }
        
    }
    
    class List {
        
        int capacity;
        HashMap<Integer, Node> keyToNode;
        Node head;
        Node tail;
        
        public List(int capacity) {
            this.capacity = capacity;
            keyToNode = new HashMap<>();
        }
        public Node add(int key) {
            if (keyToNode.containsKey(key)) {
                Node n = new Node(key);
                Node toBeDeleted = keyToNode.get(key);
                if (toBeDeleted != null && toBeDeleted.next!=null) {
                    Node next = toBeDeleted.next;
                    toBeDeleted.val = next.val;
                    if (next.next!=null) toBeDeleted.next = next.next;
                    else toBeDeleted.next = n;
                    //add node
                    tail.next=n;
                    tail = n;
                    keyToNode.put(toBeDeleted.val, toBeDeleted);
                    keyToNode.put(key, n);
                }
                else if (toBeDeleted == this.tail) { //toBedeleted.next == null
                    Node cur = head;
                    while (cur!=null && cur.next!=toBeDeleted) {
                        cur = cur.next;
                    }
                    if (cur!=null) cur.next = n;
                    tail = n;
                }
                return null;
            }
            else {
                Node n = new Node(key);
                if (keyToNode.size()<capacity) {
                    if (head==null) {
                        head = n;
                        tail = n;
                        keyToNode.put(key, n);
                    }
                    else {
                        tail.next = n;
                        tail = n;
                        keyToNode.put(key, n);
                    }
                    return null;
                }
                else {
                    Node toBeDeleted = head;
                    if (toBeDeleted!=null) {
                        head = head.next;
                        tail.next = n;
                        tail = n;
                        if (head!=null) {
                            keyToNode.remove(head.val);
                        }
                        else head = n;
                        keyToNode.put(key, n);
                    }
                    return toBeDeleted;
                }
            }
        }
    }
    class Node {
        Node next;
        int val;
        public Node(int val) {
            this.val = val;
            next = null;
        }
    }
    }
    

    I'm using LinkedList to save the set() order, and HashMap to maintain node in the list. So I can delete, insert with O(1) time. Why time limit exceeded?


  • 0
    K
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to post as answer with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.

    BTW, using LinkedHashMap is tricky.


  • 0
    K

    Your insert operation is not O(1) time. It is O(n) in worst case where n is size of the list. In function 'add' while loop will make your insertion O(n) in worst case. you can design a doubly linked list which will give you previous element of tail in O(1). Or you may use LinkedList from java collection which is doubly linkedlist.


Log in to reply
 

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