哈希算法题目：全 O(1) 的数据结构

字数 4234 2025-12-19 22:32:03

哈希算法题目：全 O(1) 的数据结构

题目描述

请你设计一个用于存储字符串计数的数据结构，并能够以常数时间复杂度执行以下操作：

inc(String key)：将 key 的计数增加 1。如果数据结构中不存在这个 key，那么插入它并将计数设置为 1。
dec(String key)：将 key 的计数减少 1。如果 key 的计数减少后为 0，那么将其从数据结构中移除。题目保证在减少之前，key 存在于数据结构中。
getMaxKey()：返回任意一个计数最大的 key。如果数据结构为空，返回空字符串 ""。
getMinKey()：返回任意一个计数最小的 key。如果数据结构为空，返回空字符串 ""。

所有操作都必须以 O(1) 的平均时间复杂度完成。

解题思路详解

这个问题的难点在于如何在修改计数（inc/dec）时，依然能在 O(1) 时间内知道当前最大和最小的计数是哪个。如果只用一个普通的哈希表（键 -> 计数），那么每次获取最大/最小值都需要 O(N) 的时间来遍历。为了实现 O(1) 的操作，我们需要一个能快速定位到“计数节点”的结构，并且这个结构能让我们在调整计数时快速找到相邻的计数节点。

核心思想：使用 “双向链表 + 哈希表” 的组合。这里的双向链表不是按插入顺序排列，而是按计数值排序的链表，每个链表节点代表一个“计数桶”，桶内存有所有具有相同计数的键。同时，我们还需要哈希表来建立“键”到其所在“计数桶”的快速映射。

步骤拆解

步骤 1：数据结构设计

我们需要定义两个核心结构：

节点（Node）：代表双向链表中的一个计数桶。
- count：这个桶对应的计数值。
- keys：一个集合（如 HashSet 或 Python 的 set），存放所有计数值等于 count 的键。使用集合是为了能在 O(1) 时间内添加或删除一个键。
- prev 和 next：指向前后节点的指针。
主数据结构（AllOne）：
- key_to_node：一个哈希表，映射从“键”（key）到其当前所在的“计数桶节点”（Node）。这让我们在 inc 或 dec 时能直接找到这个键对应的节点。
- head 和 tail：指向我们维护的有序双向链表的哑元头节点和尾节点。这个链表从左（head 之后）到右（tail 之前）的节点，其 count 值是严格递增的。初始时，head 和 tail 相互连接，链表为空。

步骤 2：链表操作辅助函数

为了方便，我们先定义两个链表操作：

_insert_node_after(Node prev_node, Node new_node)：在 prev_node 之后插入 new_node。
_remove_node(Node node)：从链表中移除 node 节点。

步骤 3：inc(String key) 操作详解

inc 的目的是将 key 的计数加 1。这意味着它需要从一个计数桶移动到下一个计数更高的桶。

检查键是否存在：
- 通过 key_to_node 查找 key 对应的节点 cur_node。
- 如果 key 不存在（即 cur_node 为 None），那么它当前的计数视为 0。我们可以认为它在计数为 0 的“虚拟桶”里。在实际操作中，我们可以将“新插入的键”看作是从“计数 0”移动到“计数 1”。
计算新的计数值：
- 新的计数值 new_count = 1（如果键不存在）或 cur_node.count + 1（如果键存在）。
寻找或创建目标桶：
- 目标桶是存放计数值为 new_count 的节点。
- 关键检查：new_count 对应的桶是否存在？即链表中 cur_node 的下一个节点（cur_node.next）的计数值是否为 new_count？
  - 如果是，那么这个节点就是目标节点 target_node。
  - 如果不是，我们需要在 cur_node 之后创建一个新的节点，其 count = new_count，并将它插入链表。
移动键到目标桶：
- 将 key 添加到 target_node.keys 集合中。
- 更新 key_to_node[key] = target_node。
清理旧桶：
- 如果 key 是原来存在的（即 cur_node 不是“虚拟桶”），那么我们需要将它从 cur_node.keys 集合中移除。
- 移除之后，检查 cur_node.keys 是否为空。如果为空，说明这个计数值已经没有任何键了，我们需要将这个节点（cur_node）从链表中完全删除，以防止链表中有空的计数桶。

步骤 4：dec(String key) 操作详解

dec 与 inc 逻辑对称，是减 1 并可能向左移动。

查找当前节点：从 key_to_node 中获取 key 当前所在的节点 cur_node。题目保证它一定存在。
计算新的计数值：new_count = cur_node.count - 1。
处理 new_count 为 0 的情况：
- 如果 new_count == 0，说明这个键的计数要归零，需要从数据结构中完全删除。
- 操作：从 cur_node.keys 中移除 key，并从 key_to_node 中删除这个键的映射。
处理 new_count 大于 0 的情况：
- 寻找或创建目标桶。这次是向左找，即检查 cur_node 的前一个节点（cur_node.prev）的计数值是否为 new_count。
- 同理，如果存在则用，不存在则新建节点插入在 cur_node.prev 之后。
- 将 key 加入目标桶的 keys 集合并更新 key_to_node 映射。
清理旧桶：
- 从 cur_node.keys 中移除 key。
- 如果移除后 cur_node.keys 为空，则将该节点从链表中删除。

步骤 5：getMaxKey() 和 getMinKey() 操作

由于我们维护了一个有序链表（count 递增），且头尾是哑元节点：

getMaxKey()：最大计数的桶就是 tail 的前一个节点（tail.prev）。只要这个节点不是 head，我们就从这个节点的 keys 集合中任意返回一个元素（比如用 Python 的 next(iter(node.keys))）。
getMinKey()：最小计数的桶就是 head 的后一个节点（head.next）。同理，只要这个节点不是 tail，就返回其 keys 集合中的任意一个元素。

这两个操作都是 O(1) 的。

一个简单的例子

假设依次执行：inc("a"), inc("b"), inc("b"), inc("c"), inc("c"), inc("c")，之后调用 getMaxKey() 和 getMinKey()。

操作过程：

inc("a"): 链表：head <-> (count=1, keys={“a”}) <-> tail
inc("b"): 因为 count=1 的桶已存在，b 加入其中。链表：head <-> (count=1, keys={“a”, “b”}) <-> tail
inc("b"): b 要从 count=1 移到 count=2。因为 count=2 的桶不存在，所以在 count=1 桶后创建它。链表：head <-> (count=1, keys={“a”}) <-> (count=2, keys={“b”}) <-> tail
inc("c"): c 加入 count=1 桶。链表：head <-> (count=1, keys={“a”, “c”}) <-> (count=2, keys={“b”}) <-> tail
inc("c"): c 从 count=1 移到 count=2。因为 c 离开，count=1 桶只剩下 {“a”}。count=2 桶已存在，c 加入其中。链表：head <-> (count=1, keys={“a”}) <-> (count=2, keys={“b”， “c”}) <-> tail
inc("c"): c 要从 count=2 移到 count=3。创建 count=3 桶。c 离开后，count=2 桶剩下 {“b”}。链表：head <-> (count=1, keys={“a”}) <-> (count=2, keys={“b”}) <-> (count=3, keys={“c”}) <-> tail
getMaxKey(): 最大桶是 tail.prev，即 count=3 桶，返回 "c"。
getMinKey(): 最小桶是 head.next，即 count=1 桶，返回 "a"。

此时如果调用 dec("a")，a 的计数变为 0，会从数据结构中删除。count=1 桶变空，被移除。链表变为：head <-> (count=2, keys={“b”}) <-> (count=3, keys={“c”}) <-> tail。此时 getMinKey() 会返回 "b"。

总结

这个 “全 O(1) 数据结构” 的核心创新点在于将相同计数的键分组到“桶”中，并用一个按计数值排序的双向链表来串联这些桶。哈希表负责从键快速定位到桶。当某个键的计数变化时，我们只需将其从一个桶的集合移动到相邻的另一个桶（或创建新桶），并维护链表的顺序。这样，获取最大/最小值就变成了访问链表两端，所有操作都实现了 O(1) 的时间复杂度。

哈希算法题目：全 O(1) 的数据结构题目描述请你设计一个用于存储字符串计数的数据结构，并能够以常数时间复杂度执行以下操作： inc(String key) ：将 key 的计数增加 1。如果数据结构中不存在这个 key ，那么插入它并将计数设置为 1。 dec(String key) ：将 key 的计数减少 1。如果 key 的计数减少后为 0，那么将其从数据结构中移除。题目保证在减少之前， key 存在于数据结构中。 getMaxKey() ：返回任意一个计数最大的 key 。如果数据结构为空，返回空字符串 "" 。 getMinKey() ：返回任意一个计数最小的 key 。如果数据结构为空，返回空字符串 "" 。所有操作都必须以 O(1) 的平均时间复杂度完成。解题思路详解这个问题的难点在于如何在修改计数（ inc / dec ）时，依然能在 O(1) 时间内知道当前最大和最小的计数是哪个。如果只用一个普通的哈希表（键 -> 计数），那么每次获取最大/最小值都需要 O(N) 的时间来遍历。为了实现 O(1) 的操作，我们需要一个能快速定位到“计数节点”的结构，并且这个结构能让我们在调整计数时快速找到相邻的计数节点。核心思想：使用 “双向链表 + 哈希表” 的组合。这里的双向链表不是按插入顺序排列，而是按计数值排序的链表，每个链表节点代表一个“计数桶”，桶内存有所有具有相同计数的键。同时，我们还需要哈希表来建立“键”到其所在“计数桶”的快速映射。步骤拆解步骤 1：数据结构设计我们需要定义两个核心结构：节点（Node）：代表双向链表中的一个计数桶。 count ：这个桶对应的计数值。 keys ：一个集合（如 HashSet 或 Python 的 set ），存放所有计数值等于 count 的键。使用集合是为了能在 O(1) 时间内添加或删除一个键。 prev 和 next ：指向前后节点的指针。主数据结构（AllOne）： key_to_node ：一个哈希表，映射从“键”（ key ）到其当前所在的“计数桶节点”（ Node ）。这让我们在 inc 或 dec 时能直接找到这个键对应的节点。 head 和 tail ：指向我们维护的有序双向链表的哑元头节点和尾节点。这个链表从左（ head 之后）到右（ tail 之前）的节点，其 count 值是严格递增的。初始时， head 和 tail 相互连接，链表为空。步骤 2：链表操作辅助函数为了方便，我们先定义两个链表操作： _insert_node_after(Node prev_node, Node new_node) ：在 prev_node 之后插入 new_node 。 _remove_node(Node node) ：从链表中移除 node 节点。步骤 3： inc(String key) 操作详解 inc 的目的是将 key 的计数加 1。这意味着它需要从一个计数桶移动到下一个计数更高的桶。检查键是否存在：通过 key_to_node 查找 key 对应的节点 cur_node 。如果 key 不存在（即 cur_node 为 None ），那么它当前的计数视为 0。我们可以认为它在计数为 0 的“虚拟桶”里。在实际操作中，我们可以将“新插入的键”看作是从“计数 0”移动到“计数 1”。计算新的计数值：新的计数值 new_count = 1 （如果键不存在）或 cur_node.count + 1 （如果键存在）。寻找或创建目标桶：目标桶是存放计数值为 new_count 的节点。关键检查： new_count 对应的桶是否存在？即链表中 cur_node 的下一个节点（ cur_node.next ）的计数值是否为 new_count ？如果是，那么这个节点就是目标节点 target_node 。如果不是，我们需要在 cur_node 之后创建一个新的节点，其 count = new_count ，并将它插入链表。移动键到目标桶：将 key 添加到 target_node.keys 集合中。更新 key_to_node[key] = target_node 。清理旧桶：如果 key 是原来存在的（即 cur_node 不是“虚拟桶”），那么我们需要将它从 cur_node.keys 集合中移除。移除之后，检查 cur_node.keys 是否为空。如果为空，说明这个计数值已经没有任何键了，我们需要将这个节点（ cur_node ）从链表中完全删除，以防止链表中有空的计数桶。步骤 4： dec(String key) 操作详解 dec 与 inc 逻辑对称，是减 1 并可能向左移动。查找当前节点：从 key_to_node 中获取 key 当前所在的节点 cur_node 。题目保证它一定存在。计算新的计数值： new_count = cur_node.count - 1 。处理 new_ count 为 0 的情况：如果 new_count == 0 ，说明这个键的计数要归零，需要从数据结构中完全删除。操作：从 cur_node.keys 中移除 key ，并从 key_to_node 中删除这个键的映射。处理 new_ count 大于 0 的情况：寻找或创建目标桶。这次是向左找，即检查 cur_node 的前一个节点（ cur_node.prev ）的计数值是否为 new_count 。同理，如果存在则用，不存在则新建节点插入在 cur_node.prev 之后。将 key 加入目标桶的 keys 集合并更新 key_to_node 映射。清理旧桶：从 cur_node.keys 中移除 key 。如果移除后 cur_node.keys 为空，则将该节点从链表中删除。步骤 5： getMaxKey() 和 getMinKey() 操作由于我们维护了一个有序链表（ count 递增），且头尾是哑元节点： getMaxKey() ：最大计数的桶就是 tail 的前一个节点（ tail.prev ）。只要这个节点不是 head ，我们就从这个节点的 keys 集合中任意返回一个元素（比如用 Python 的 next(iter(node.keys)) ）。 getMinKey() ：最小计数的桶就是 head 的后一个节点（ head.next ）。同理，只要这个节点不是 tail ，就返回其 keys 集合中的任意一个元素。这两个操作都是 O(1) 的。一个简单的例子假设依次执行： inc("a") , inc("b") , inc("b") , inc("c") , inc("c") , inc("c") ，之后调用 getMaxKey() 和 getMinKey() 。操作过程： inc("a") : 链表： head <-> (count=1, keys={“a”}) <-> tail inc("b") : 因为 count=1 的桶已存在， b 加入其中。链表： head <-> (count=1, keys={“a”, “b”}) <-> tail inc("b") : b 要从 count=1 移到 count=2 。因为 count=2 的桶不存在，所以在 count=1 桶后创建它。链表： head <-> (count=1, keys={“a”}) <-> (count=2, keys={“b”}) <-> tail inc("c") : c 加入 count=1 桶。链表： head <-> (count=1, keys={“a”, “c”}) <-> (count=2, keys={“b”}) <-> tail inc("c") : c 从 count=1 移到 count=2 。因为 c 离开， count=1 桶只剩下 {“a”} 。 count=2 桶已存在， c 加入其中。链表： head <-> (count=1, keys={“a”}) <-> (count=2, keys={“b”， “c”}) <-> tail inc("c") : c 要从 count=2 移到 count=3 。创建 count=3 桶。 c 离开后， count=2 桶剩下 {“b”} 。链表： head <-> (count=1, keys={“a”}) <-> (count=2, keys={“b”}) <-> (count=3, keys={“c”}) <-> tail getMaxKey() : 最大桶是 tail.prev ，即 count=3 桶，返回 "c" 。 getMinKey() : 最小桶是 head.next ，即 count=1 桶，返回 "a" 。此时如果调用 dec("a") ， a 的计数变为 0，会从数据结构中删除。 count=1 桶变空，被移除。链表变为： head <-> (count=2, keys={“b”}) <-> (count=3, keys={“c”}) <-> tail 。此时 getMinKey() 会返回 "b" 。总结这个 “全 O(1) 数据结构” 的核心创新点在于将相同计数的键分组到“桶”中，并用一个按计数值排序的双向链表来串联这些桶。哈希表负责从键快速定位到桶。当某个键的计数变化时，我们只需将其从一个桶的集合移动到相邻的另一个桶（或创建新桶），并维护链表的顺序。这样，获取最大/最小值就变成了访问链表两端，所有操作都实现了 O(1) 的时间复杂度。