题目

标题和出处

标题：全 O(1) 的数据结构

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

难度

10 级

题目描述

要求

设计一个存储字符串计数的数据结构，并能返回最小计数和最大计数的字符串。要求所有操作的时间复杂度是 $\text{O(1)}$。

实现 $\text{AllOne}$ 类：

• $\text{AllOne()}$ 初始化数据结构的对象。
• $\text{inc(String key)}$ 将字符串 $\text{key}$ 的计数加 $\text{1}$。如果 $\text{key}$ 不在数据结构中，将其插入并将计数设为 $\text{1}$。
• $\text{dec(String key)}$ 将字符串 $\text{key}$ 的计数减 $\text{1}$。如果在减少计数之后，$\text{key}$ 的计数为 $\text{0}$，将其从数据结构中删除。题目保证在减少计数之前 $\text{key}$ 在数据结构中。
• $\text{getMaxKey()}$ 返回计数最大的任意一个 $\text{key}$。如果没有元素存在，返回一个空字符串 $\text{""}$。
• $\text{getMinKey()}$ 返回计数最小的任意一个 $\text{key}$。如果没有元素存在，返回一个空字符串 $\text{""}$。

示例

示例 1：

输入：
$\text{["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]}$
$\text{[[], ["hello"], ["hello"], [], [], ["leet"], [], []]}$
输出：
$\text{[null, null, null, "hello", "hello", null, "hello", "leet"]}$
解释：
$\text{AllOne allOne = new AllOne();}$
$\text{allOne.inc("hello");}$
$\text{allOne.inc("hello");}$
$\text{allOne.getMaxKey();}$ // 返回 $\text{"hello"}$
$\text{allOne.getMinKey();}$ // 返回 $\text{"hello"}$
$\text{allOne.inc("leet");}$
$\text{allOne.getMaxKey();}$ // 返回 $\text{"hello"}$
$\text{allOne.getMinKey();}$ // 返回 $\text{"leet"}$

数据范围

• $\text{1}\le \text{key.length}\le \text{10}$
• $\text{key}$ 由小写英语字母组成
• 题目保证调用 $\text{dec}$ 时，$\text{key}$ 在数据结构中
• 最多调用 $\text{5}\times {\text{10}}^{\text{4}}$ 次 $\text{inc}$、$\text{dec}$、$\text{getMaxKey}$ 和 $\text{getMinKey}$

解法

思路和算法

为了维护每个关键字的计数，需要对每个关键字创建一个结点，以及对每个计数维护一个双向链表，每个双向链表由特定计数的全部结点组成。为了获得最大计数的关键字和最小计数的关键字，不同的计数之间也需要维护一个双向链表，存储计数的双向链表满足单调性。因此，实现全 $O(1)$ 的数据结构需要使用两种双向链表，分别用于存储关键字对应的结点和计数对应的结点，这两种双向链表分别为关键字链表和计数链表，这两种双向链表中的结点分别为关键字结点和计数结点。

• 关键字链表中每个结点存储关键字、计数以及该结点的前一个结点和后一个结点，结点顺序为从头结点到尾结点依次按照添加时间升序排列。

• 计数链表中的每个结点存储计数对应的关键字链表以及该结点的前一个结点和后一个结点，结点顺序为从头结点到尾结点依次按照计数升序排列。

为了便于操作，关键字链表和计数链表都需要维护伪头结点和伪尾结点，链表的实际头结点为伪头结点的后一个结点，链表的实际尾结点为伪尾结点的前一个结点（只有当链表不为空时才存在实际头结点和实际尾结点）。初始时，伪头结点和伪尾结点相邻。

全 $O(1)$ 的数据结构中，需要维护两个哈希表，关键字哈希表存储关键字对应的关键字结点，计数哈希表存储计数对应的计数结点，以及需要维护计数链表。

构造方法中，将两个哈希表和计数链表初始化。

对于 $\text{inc}$ 操作，首先判断关键字哈希表中是否存在关键字 $\text{key}$，然后分别执行相应的操作。

• 如果关键字哈希表中存在关键字 $\text{key}$，做法如下。

  1. 在关键字哈希表中得到 $\text{key}$ 对应的关键字结点，将该关键字结点的计数加 $1$，关键字结点的计数在更新之前和更新之后分别为原计数和新计数。

  2. 在计数哈希表中得到原计数对应的计数结点，该计数结点为原计数结点，将该关键字结点从原计数结点中的关键字链表中删除。

  3. 如果计数哈希表中不存在新计数，则新建一个计数结点，在计数哈希表中添加新计数和该计数结点的对应关系，并将该计数结点添加到计数链表中的原计数结点的后面一个结点的位置。如果计数哈希表中已经存在新计数，则不执行这一步。

  4. 在计数哈希表中得到新计数对应的计数结点，该计数结点为新计数结点，将该关键字结点添加到新计数结点中的关键字链表的末尾。

  5. 如果原计数结点中的关键字链表变为空，则将原计数从计数哈希表中删除，并将原计数结点从计数链表中删除。由于添加新计数结点的位置需要根据原计数结点定位，因此删除原计数结点的操作应该在添加新计数结点的操作之后。

• 如果关键字哈希表中不存在关键字 $\text{key}$，做法如下。

  1. 根据 $\text{key}$ 创建关键字结点，在关键字哈希表中添加 $\text{key}$ 和该结点的对应关系。新关键字结点的计数是 $1$。

  2. 如果计数哈希表中不存在计数 $1$，则新建一个计数结点，在计数结点中添加计数 $1$ 和该计数结点的对应关系，并将该计数结点添加到计数链表中的伪头结点的后面一个结点的位置（因为计数链表中不存在计数 $0$ 对应的结点，如果计数 $1$ 存在则一定是最小计数）。如果计数哈希表中已经存在计数 $1$，则不执行这一步。

  3. 在计数哈希表中得到计数 $1$ 对应的计数结点，将该关键字结点添加到该计数结点中的关键字链表的末尾。

对于 $\text{dec}$ 操作，做法如下。

1. 在关键字哈希表中得到 $\text{key}$ 对应的关键字结点，将该关键字结点的计数减 $1$，关键字结点的计数在更新之前和更新之后分别为原计数和新计数。

2. 在计数哈希表中得到原计数对应的计数结点，该计数结点为原计数结点，将该关键字结点从原计数结点中的关键字链表中删除。

3. 判断新计数是否大于 $0$，执行相应的操作。

   • 如果新计数大于 $0$，则需要根据新计数更新状态。

     1. 如果计数哈希表中不存在新计数，则新建一个计数结点，在计数哈希表中添加新计数和该计数结点的对应关系，并将该计数结点添加到计数链表中的原计数结点的前面一个结点的位置。如果计数哈希表中已经存在新计数，则不执行这一步。

     2. 在计数哈希表中得到新计数对应的计数结点，该计数结点为新计数结点，将该关键字结点添加到新计数结点中的关键字链表的末尾。

   • 如果新计数等于 $0$，则将 $\text{key}$ 从关键字哈希表中删除。

4. 如果原计数结点中的关键字链表变为空，则将原计数从计数哈希表中删除，并将原计数结点从计数链表中删除。由于添加新计数结点的位置需要根据原计数结点定位，因此删除原计数结点的操作应该在添加新计数结点的操作之后。

对于 $\text{getMaxKey}$ 操作，如果计数链表为空则返回空字符串，否则获得计数链表的实际尾结点中的关键字链表并返回关键字链表的实际头结点。

对于 $\text{getMinKey}$ 操作，如果计数链表为空则返回空字符串，否则获得计数链表的实际头结点中的关键字链表并返回关键字链表的实际头结点。

由于每次 $\text{inc}$ 操作和 $\text{dec}$ 操作都是对哈希表和双向链表的操作，每次 $\text{getMaxKey}$ 操作和 $\text{getMinKey}$ 操作都是从双向链表的头结点或尾结点中获得对应的值，哈希表操作和在链表中查看、添加和删除结点操作的时间都是 $O(1)$，因此各项操作的时间复杂度都是 $O(1)$。这里将字符串操作的时间视为 $O(1)$。

代码

class AllOne {
    private class Node {
        private String key;
        private int count;
        private Node prev;
        private Node next;

        public Node() {
            this("");
        }

        public Node(String key) {
            this.key = key;
            count = 1;
            prev = null;
            next = null;
        }

        public String getKey() {
            return key;
        }

        public int getCount() {
            return count;
        }

        public void increaseCount() {
            count++;
        }

        public void decreaseCount() {
            count--;
        }

        public Node getPrev() {
            return prev;
        }

        public void setPrev(Node prev) {
            this.prev = prev;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    private class DoublyLinkedList {
        private Node pseudoHead;
        private Node pseudoTail;
        private int size;

        public DoublyLinkedList() {
            pseudoHead = new Node();
            pseudoTail = new Node();
            pseudoHead.setNext(pseudoTail);
            pseudoTail.setPrev(pseudoHead);
            size = 0;
        }

        public void addNode(Node node) {
            Node prevNode = pseudoTail.getPrev();
            node.setPrev(prevNode);
            prevNode.setNext(node);
            node.setNext(pseudoTail);
            pseudoTail.setPrev(node);
            size++;
        }

        public void removeNode(Node node) {
            Node prev = node.getPrev();
            Node next = node.getNext();
            prev.setNext(next);
            next.setPrev(prev);
            size--;
        }

        public Node getHead() {
            return pseudoHead.getNext();
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }

    private class CountListNode {
        private DoublyLinkedList list;
        private CountListNode prevCountListNode;
        private CountListNode nextCountListNode;

        public CountListNode() {
            list = new DoublyLinkedList();
            prevCountListNode = null;
            nextCountListNode = null;
        }

        public String getKey() {
            return list.getHead().getKey();
        }

        public void addNode(Node node) {
            list.addNode(node);
        }

        public void removeNode(Node node) {
            list.removeNode(node);
        }

        public boolean isEmpty() {
            return list.isEmpty();
        }

        public CountListNode getPrev() {
            return prevCountListNode;
        }

        public void setPrev(CountListNode prevCountListNode) {
            this.prevCountListNode = prevCountListNode;
        }

        public CountListNode getNext() {
            return nextCountListNode;
        }

        public void setNext(CountListNode nextCountListNode) {
            this.nextCountListNode = nextCountListNode;
        }
    }

    private class CountList {
        private CountListNode pseudoHeadCountListNode;
        private CountListNode pseudoTailCountListNode;

        public CountList() {
            pseudoHeadCountListNode = new CountListNode();
            pseudoTailCountListNode = new CountListNode();
            pseudoHeadCountListNode.setNext(pseudoTailCountListNode);
            pseudoTailCountListNode.setPrev(pseudoHeadCountListNode);
        }

        public void addAfter(CountListNode countListNode, CountListNode original) {
            CountListNode next = original.getNext();
            countListNode.setPrev(original);
            original.setNext(countListNode);
            countListNode.setNext(next);
            next.setPrev(countListNode);
        }

        public void addBefore(CountListNode countListNode, CountListNode original) {
            CountListNode prev = original.getPrev();
            countListNode.setNext(original);
            original.setPrev(countListNode);
            countListNode.setPrev(prev);
            prev.setNext(countListNode);
        }

        public void addAtHead(CountListNode countListNode) {
            addAfter(countListNode, pseudoHeadCountListNode);
        }

        public void remove(CountListNode countListNode) {
            CountListNode prevCountListNode = countListNode.getPrev();
            CountListNode nextCountListNode = countListNode.getNext();
            prevCountListNode.setNext(nextCountListNode);
            nextCountListNode.setPrev(prevCountListNode);
        }

        public boolean isEmpty() {
            return pseudoHeadCountListNode.getNext() == pseudoTailCountListNode;
        }

        public CountListNode getHead() {
            return pseudoHeadCountListNode.getNext();
        }

        public CountListNode getTail() {
            return pseudoTailCountListNode.getPrev();
        }
    }

    private Map<String, Node> keyNodeMap;
    private Map<Integer, CountListNode> countListNodeMap;
    private CountList countList;

    public AllOne() {
        keyNodeMap = new HashMap<String, Node>();
        countListNodeMap = new HashMap<Integer, CountListNode>();
        countList = new CountList();
    }

    public void inc(String key) {
        if (keyNodeMap.containsKey(key)) {
            Node node = keyNodeMap.get(key);
            int prevCount = node.getCount();
            node.increaseCount();
            int currCount = node.getCount();
            CountListNode prevCountListNode = countListNodeMap.get(prevCount);
            prevCountListNode.removeNode(node);
            if (!countListNodeMap.containsKey(currCount)) {
                countListNodeMap.put(currCount, new CountListNode());
                countList.addAfter(countListNodeMap.get(currCount), prevCountListNode);
            }
            CountListNode currCountListNode = countListNodeMap.get(currCount);
            currCountListNode.addNode(node);
            if (prevCountListNode.isEmpty()) {
                countListNodeMap.remove(prevCount);
                countList.remove(prevCountListNode);
            }
        } else {
            Node node = new Node(key);
            keyNodeMap.put(key, node);
            if (!countListNodeMap.containsKey(1)) {
                countListNodeMap.put(1, new CountListNode());
                countList.addAtHead(countListNodeMap.get(1));
            }
            CountListNode currCountListNode = countListNodeMap.get(1);
            currCountListNode.addNode(node);
        }
    }

    public void dec(String key) {
        Node node = keyNodeMap.get(key);
        int prevCount = node.getCount();
        node.decreaseCount();
        int currCount = node.getCount();
        CountListNode prevCountListNode = countListNodeMap.get(prevCount);
        prevCountListNode.removeNode(node);
        if (currCount > 0) {
            if (!countListNodeMap.containsKey(currCount)) {
                countListNodeMap.put(currCount, new CountListNode());
                countList.addBefore(countListNodeMap.get(currCount), prevCountListNode);
            }
            CountListNode currCountListNode = countListNodeMap.get(currCount);
            currCountListNode.addNode(node);
        } else {
            keyNodeMap.remove(key);
        }
        if (prevCountListNode.isEmpty()) {
            countListNodeMap.remove(prevCount);
            countList.remove(prevCountListNode);
        }
    }

    public String getMaxKey() {
        if (countList.isEmpty()) {
            return "";
        }
        CountListNode maxCountListNode = countList.getTail();
        return maxCountListNode.getKey();
    }

    public String getMinKey() {
        if (countList.isEmpty()) {
            return "";
        }
        CountListNode minCountListNode = countList.getHead();
        return minCountListNode.getKey();
    }
}

复杂度分析

• 时间复杂度：构造方法和各项操作的时间复杂度都是 $O(1)$。这里将字符串操作的时间视为 $O(1)$。

• 空间复杂度：$O(n)$，其中 $n$ 是不同关键字的数量。空间复杂度主要取决于哈希表和双向链表，元素个数为不同关键字的数量。这里将字符串占用的空间视为 $O(1)$。

后记

读者也许已经发现，这道题和「LFU 缓存」有相似之处，都可以使用哈希表和双向链表实现。但是这道题还有将计数减少的操作和获得计数最大的关键字的操作，因此这道题的思维难度和实现难度都更高。这道题最大的难点在于维护计数链表。只有充分理解哈希表和双向链表，才能正确实现这道题。

由于 $\text{getMaxKey}$ 操作和 $\text{getMinKey}$ 操作只要求返回满足特定计数（最大计数或最小计数）的任意一个关键字，因此不需要维护相同计数的关键字之间的顺序，上述解法中的关键字链表也可以换成哈希集合，读者可以自行尝试实现。