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

题目描述

这是 LeetCode 上的 432. 全 O(1) 的数据结构 ，难度为 困难。

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

实现 AllOne 类：

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入
["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 * 10^4$ 次

双向链表 + 哈希表

题目要求我们支持 $O(1)$ 的查询和修改，其中查询只需返回任意一个计数次数「最多」和「最少」的元素即可（如果有）。

虽然插入的字符串长度不超过 $10$（该数据范围的含义为字符串的哈希计算消耗可看作常数），但单纯的使用「哈希表」仅能做到 $O(1)$ 的计数，无法做到 $O(1)$ 查询。

我们可以采取和 实现一个 LRUCache & 实现一个 LFUCache 类似的思路，通过自定义节点并手写双链表来实现。

定义一个节点类 Node，除了包含用于实现双向链表的 left 和 right 以外，还包含一个数值类型的变量 cnt， 用于记录该节点存储的是计数次数为多少的元素，以及一个 Set 类型的容器，用于支持 $O(1)$ 插入和删除元素，记作 set。

同时为了快速知道某个字符串属于哪个 Node，我们还需要开一个「哈希表」进行定位（以字符串为哈希表的键，字符串所在 Node 作为值），当定位到字符串对应的 Node 之后则可以利用双向链表的 $O(1)$ 增加/修改/删除。

在双向链表中，起始只有两个哨兵节点 hh 和 tt ，当进行若干 inc/dec 操作后的基本形态为：

的数据结构（困难）/image_0.png)

对应几个操作：

inc/dec 操作：当对一个字符串 key 进行「增加计数」或「减少计数」时，先在哈希表中看 key 是否存在：

  • 若存在：根据其所属的 Node 的计数 cnt 为多少，并结合当前是「增加计数」还是「减少计数」来决定是找 Node 的「右节点」还是「左节点」，同时检查相邻节点的计数值 cnt 是否为目标值，对应要检查数值是 $cnt + 1$ 和 $cnt - 1$：
    • 若相邻节点的 cnt 为目标值：即目标节点存在，将 key 从原 Node 的 set 集合中移除，并添加到目标节点的集合中，更新哈希表；
    • 若相邻节点的 cnt 不是目标值：则需要创建相应的目标节点，并构建双向链表关系，把 key 存入新创建的目标节点，更新哈希表。
  • 若不存在（只能是 inc 操作）：查找是否存在 $cnt = 1$ 的节点（也就是检查 hh.right 节点的计数值）：
    • 如果存在 $cnt = 1$ 的目标节点：将 key 添加到目标节点的 set 集合中，更新哈希表；
    • 若不存在 $cnt = 1$ 的目标节点：创建相应的节点，并构建双向关系，并构建双向链表关系，把 key 存入新创建的目标节点，更新哈希表。

getMaxKey/getMinKey 操作：分别从 tt.left 和 hh.right 中尝试查找，如果存在非哨兵节点，则从节点的 set 集合中取任意元素进行返回，否则返回空串。

最后，为了确保 getMaxKey/getMinKey 操作能够严格 $O(1)$，我们在进行 inc/dec 操作时我们需要对一些 set 容量为 $0$ 的节点进行释放，即解除其所在双向链表的关系。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class AllOne {

    class Node {
        int cnt;
        Set<String> set = new HashSet<>();
        Node left, right;
        Node(int _cnt) {
            cnt = _cnt;
        }
    }
    
    Node hh, tt;
    Map<String, Node> map = new HashMap<>();
    public AllOne() {
        hh = new Node(-1000); tt = new Node(-1000);
        hh.right = tt; tt.left = hh;
    }

    void clear(Node node) {
        if (node.set.size() == 0) {
            node.left.right = node.right;
            node.right.left = node.left;
        }
    }
    
    public void inc(String key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.set.remove(key);
            int cnt = node.cnt;
            Node next = null;
            if (node.right.cnt == cnt + 1) {
                next = node.right;
            } else {
                next = new Node(cnt + 1);
                next.right = node.right;
                next.left = node;
                node.right.left = next;
                node.right = next;
            }
            next.set.add(key);
            map.put(key, next);
            clear(node);
        } else {
            Node node = null;
            if (hh.right.cnt == 1) {
                node = hh.right;
            } else {
                node = new Node(1);
                node.right = hh.right;
                node.left = hh;
                hh.right.left = node;
                hh.right = node;
            }
            node.set.add(key);
            map.put(key, node);
        }
    }
    
    public void dec(String key) {
        Node node = map.get(key);
        node.set.remove(key);
        int cnt = node.cnt;
        if (cnt == 1) {
            map.remove(key);
        } else {
            Node prev = null;
            if (node.left.cnt == cnt - 1) {
                prev = node.left;
            } else {
                prev = new Node(cnt - 1);
                prev.right = node;
                prev.left = node.left;
                node.left.right = prev;
                node.left = prev;
            }
            prev.set.add(key);
            map.put(key, prev);
        }
        clear(node);
    }
    
    public String getMaxKey() {
        Node node = tt.left;
        for (String str : node.set) return str;
        return "";
    }
    
    public String getMinKey() {
        Node node = hh.right;
        for (String str : node.set) return str;
        return "";
    }
}

  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.432 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。