[数据结构与算法]432_全O(1)的数据结构

432_全O(1)的数据结构

432. 全 O(1) 的数据结构

请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 AllOne 类：

• AllOne() 初始化数据结构的对象。
• inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1的 key 。
• dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
• getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
• getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。

示例：

输入
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
输出
[null, null, null, "hello", "hello", null, "hello", "leet"]

解释
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "hello"
allOne.inc("leet");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "leet"

提示：

• 1 <= key.length <= 10
• key 由小写英文字母组成
• 测试用例保证：在每次调用 dec 时，数据结构中总存在 key
• 最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 104 次

Related Topics

设计

哈希表

链表

双向链表

哈希表+双向链表

哈希表维护key和node节点，然后在维护一个双向链表中存储Node，这样就可以O1的时间复杂度查找最大值，也可以以O1的时间复杂度进行插入和删除。

class AllOne {
    private HashMap<String,Node> map;
    private Node head;
    private Node tail;
    public AllOne() {
        map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    
    public void inc(String key) {
        Node node;
        if(map.containsKey(key)){
            node = map.get(key);
            node.value += 1;
            moveFront(node);
        }else{
            node = new Node(key,1);
            //插入到尾部
            insert(node,tail);
            map.put(key,node);
        }
    }
    
    public void dec(String key) {
        Node node = map.get(key);
        if(node.value == 1){
            delete(node);
            map.remove(key);
        }else{
            node.value -= 1;
            moveLater(node);
        }
    }
    
    public String getMaxKey() {
        return head.next == tail ? "" : head.next.key;
    }
    
    public String getMinKey() {
        return head.next == tail ? "" : tail.prev.key;
    }
    public void moveLater(Node node){
        Node p = node.next;
        while (p!=tail && p.value>node.value){
            p = p.next;
        }
        delete(node);
        insert(node,p);
    }
    public void moveFront(Node node){
        //把node向前移动到合适的位置
        Node p = node.prev;
        while (p != head && p.value < node.value){
            p = p.prev;
        }
        delete(node);
        insert(node,p.next);
    }
    //删除这个节点
    public void delete(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
    }
    //往index前面插入node
    public void insert(Node node,Node index){
        node.prev = index.prev;
        node.next = index;
        node.prev.next = node;
        node.next.prev = node;
    }
    class Node{
        String key;
        int value;
        Node prev;
        Node next;
        public Node(){

        }
        public Node(String key,int value){
            this.key = key;
            this.value = value;
        }

    }
}