Java AC code, but slow...


  • 0
    S
    public class AllOne {
    
        Map<String, Node> map = new HashMap<>();
        DList list = new DList();
        
        /** Initialize your data structure here. */
        public AllOne() {
            
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            Node node = map.get(key);
            if (node == null) {
                node = list.add(key);
            } else {
                node = list.increment(node, key);
            }
            map.put(key, node);
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            Node node = map.get(key);
            if (node != null) {
                if (node.val == 1) {
                    map.remove(key);
                    list.delete(node, key);
                } else {
                    node = list.decrement(node, key);
                    map.put(key, node);
                }
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            return list.head == null ? "" : list.head.getKey();
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            return list.tail == null ? "" : list.tail.getKey();
        }
        
        class DList {
            Node head, tail;
            
            public DList() {
                head = tail = null;
            }
            
            public Node add(String key) {
                if (tail == null) {
                    head = tail = new Node(1);
                    head.addKey(key);
                } else {
                    if (tail.val == 1) {
                        tail.addKey(key);
                    } else {
                        Node node = new Node(1);
                        node.addKey(key);
                        tail.next = node;
                        node.prev = tail;
                        tail = node;
                    }
                }
                return tail;
            }
            
            public void delete(Node node, String key) {
                node.removeKey(key);
                if (node.empty()) {
                    Node prev = node.prev;
                    Node next = node.next;
                    if (prev != null) {
                        prev.next = next;
                    }
                    if (next != null) {
                        next.prev = prev;
                    }
                    if (node == head) {
                        head = next;
                    }
                    if (node == tail) {
                        tail = prev;
                    }
                    node.prev = node.next = null;
                }
            }
            
            public Node increment(Node node, String key) {
                Node prev = node.prev;
                Node retNode = null;
                int val = node.val + 1;
                if (prev != null) {
                    if (prev.val == val) {
                        prev.addKey(key);
                        retNode = prev;
                    } else {
                        Node newNode = new Node(val);
                        newNode.addKey(key);
                        newNode.prev = prev;
                        newNode.next = node;
                        prev.next = newNode;
                        node.prev = newNode;
                        retNode = newNode;
                    }
                } else {
                    Node newNode = new Node(val);
                    newNode.addKey(key);
                    newNode.next = node;
                    node.prev = newNode;
                    head = newNode;
                    retNode = newNode;
                }
                delete(node, key);
                return retNode;
            }
            
            public Node decrement(Node node, String key) {
                Node next = node.next;
                Node retNode;
                int val = node.val - 1;
                if (next != null) {
                    if (next.val == val) {
                        next.addKey(key);
                        retNode = next;
                    } else {
                        Node newNode = new Node(val);
                        newNode.addKey(key);
                        newNode.prev = node;
                        newNode.next = next;
                        node.next = newNode;
                        next.prev = newNode;
                        retNode = newNode;
                    }
                } else {
                    Node newNode = new Node(val);
                    newNode.addKey(key);
                    newNode.prev = node;
                    tail = newNode;
                    retNode = newNode;
                }
                delete(node, key);
                return retNode;
            }
        }
        
        class Node {
            Node prev, next;
            int val;
            Set<String> keys;
            
            public Node(int v) {
                keys = new HashSet<String>();
                val = v;
                prev = next = null;
            }
            
            public void addKey(String key) {
                keys.add(key);
            }
            
            public void removeKey(String key) {
                keys.remove(key);
            }
            
            public boolean empty() {
                return keys.isEmpty();
            }
            
            public String getKey() {
                for (String key : keys) {
                    return key;
                }
                return "";
            }
        }
    }
    

    `


  • 0
    S

    Should be doing all operations in O(1), but takes 118ms which is slower than some solutions here with O(logn)


Log in to reply
 

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