“全 O(1) 的数据结构”
字数 3658 2025-12-23 02:16:12

好的，我们随机选择一个哈希算法领域尚未讲过的题目。根据你的历史列表，“全 O(1) 的数据结构” 这个经典题目尚未被详细讲解过。

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

题目描述：
请你设计一个数据结构，用于高效地存储字符串键及其对应的计数值（非负整数），并支持所有操作在常数平均时间复杂度 O(1) 内完成。需要支持以下四种操作：

  1. inc(String key)：将键 key 的计数增加 1。如果 key 不存在，则插入其初始计数为 1。
  2. dec(String key)：将键 key 的计数减少 1。如果 key 的计数在减少后变为 0，则从数据结构中移除该键。如果 key 不存在，此函数不做任何操作。
  3. getMaxKey()：返回当前计数最大的任意一个键。如果数据结构为空，返回空字符串 ""。
  4. getMinKey()：返回当前计数最小的任意一个键。如果数据结构为空，返回空字符串 ""。

核心挑战：
既要支持键到值的快速查找和修改（这可以通过哈希表实现），又要支持在修改计数值后，能迅速找到新的最大值和最小值。而简单地维护一个最大值和最小值变量是不行的，因为当这个唯一的最大/最小值被dec操作后，我们需要找到“次大/次小”的值。

解题思路与过程详解

这个问题的关键在于将相同计数的键组织在一起，并维护一个按计数严格递增的链表。链表的每个节点代表一个“计数桶”，桶内存储所有计数值相同的键。

第一步：数据结构设计

我们需要三个核心组件：

  1. 哈希表 keyMap：键 String -> 节点 Node。用于通过键快速定位到它当前所在的计数桶节点。
  2. 双向链表 Node：链表节点代表一个计数值 count。节点内包含：
    • count: 该桶的计数值。
    • keys: 一个哈希集合（如 HashSet<String>），存储所有计数值为 count 的键。
    • prev, next: 指向前驱和后继节点的指针。
  3. 链表的虚拟头尾节点：为了方便插入和删除操作，我们初始化一个双向链表，包含一个 head（计数为0的虚拟最小节点）和一个 tail（计数为0的虚拟最大节点）。

为什么是双向链表？
因为计数的变化是相邻的（+1或-1）。当某个键的计数从 c 变为 c+1 时，它需要从代表 c 的桶移动到代表 c+1 的桶。如果 c+1 的桶不存在，我们需要在链表中 c 桶的后面插入一个新的桶。双向链表可以让我们在 O(1) 时间内完成节点的插入和删除。

链表顺序：链表从 head 到 tail 是严格递增的，即 head.count < node1.count < node2.count < ... < tail.count。

初始状态：链表只有 head <-> tail。

第二步：操作流程分析

我们以 inc(“hello”) 为例，假设初始 hello 不存在。

1. inc(String key)

  • 情况A：键不存在（keyMap 中无此键）。

    • 此时该键的计数应从 0 变为 1。
    • 检查 head.next 是否是计数值为 1 的桶。
      • 如果是，将 ”hello” 加入该桶的 keys 集合。
      • 如果不是，在 head 和 head.next 之间插入一个新的计数值为 1 的桶，并将 ”hello” 加入其 keys 集合。
    • 在 keyMap 中记录 ”hello” -> 这个新桶（节点1）。
    • 最大值检查：由于我们是在链表最前面（最小值端）插入，最大值 tail.prev 不会受影响（除非之前链表为空，那么新插入的节点既是最大也是最小）。

  • 情况B：键已存在，假设当前在计数值为 c 的桶 nodeC 中。

    • 新计数应为 c+1。
    • 将 key 从 nodeC.keys 集合中移除。
    • 检查 nodeC.next 是否是计数值为 c+1 的桶。
      • 如果是，将 key 加入 nodeC.next.keys。
      • 如果不是，在 nodeC 和 nodeC.next 之间插入一个新的计数值为 c+1 的桶，并将 key 加入其 keys 集合。
    • 更新 keyMap 中 key 的映射关系，指向这个新桶（c+1 的桶）。
    • 清理：如果移除 key 后，nodeC.keys 变为空（即没有任何键的计数是 c 了），则需要将 nodeC 从链表中删除。
    • 最大值检查：如果 nodeC 恰好是原来的最大桶（tail.prev），并且我们创建了一个 c+1 的新桶，那么这个新桶就成为了新的最大桶。

2. dec(String key)

  • 思路与 inc 对称，但方向相反。
  • 如果键不存在，直接返回。
  • 找到键所在的桶 nodeC（计数为 c）。
  • 将 key 从 nodeC.keys 中移除。
  • 如果 c == 1，递减后计数为0，直接从 keyMap 中删除此键。
  • 如果 c > 1，新计数为 c-1。
    • 检查 nodeC.prev 是否是计数值为 c-1 的桶。
      • 如果是，将 key 加入 nodeC.prev.keys。
      • 如果不是，在 nodeC.prev 和 nodeC 之间插入一个新的计数值为 c-1 的桶，并将 key 加入。
    • 更新 keyMap。
  • 清理：同样，如果移除 key 后 nodeC.keys 为空，则将 nodeC 从链表中删除。
  • 最小值检查：如果 nodeC 恰好是原来的最小桶（head.next），并且我们创建了一个 c-1 的新桶，那么这个新桶就成为了新的最小桶。

3. getMaxKey() 与 getMinKey()

  • 这两个操作变得非常简单。
  • getMaxKey()：如果链表有效（head.next != tail），则返回 tail.prev.keys 集合中的任意一个元素（例如用迭代器的 .next()）。
  • getMinKey()：如果链表有效，则返回 head.next.keys 集合中的任意一个元素。

第三步：关键点与复杂度分析

  1. 为什么是 O(1) 时间？

    • keyMap 的查找、插入、删除是 O(1) 平均。
    • 链表中节点的插入（在已知位置后）、删除是 O(1)。
    • 从一个 HashSet 中增删一个元素是 O(1) 平均。
    • 因此，inc 和 dec 的所有步骤都是常数时间操作。
    • getMaxKey 和 getMinKey 是直接访问，也是 O(1)。

  2. 边界情况处理：

    • 空数据结构：head.next == tail。此时 getMaxKey 和 getMinKey 应返回 ””。
    • 计数桶为空：当一个桶的 keys 集合变空时，必须将其从链表中删除，否则会干扰 getMaxKey/getMinKey 的正确性，并造成内存泄漏。
    • 从1减到0：dec 操作使计数变为0时，键应从 keyMap 中移除，且不需要创建计数为0的新桶（我们的虚拟 head 就是计数0的桶，但它不存储实际键）。

第四步：示例推演

假设我们依次执行：

  1. inc(“a”) -> (a:1)。链表：head <-> [1: {a}] <-> tail。Max=a, Min=a。
  2. inc(“b”) -> (b:1)。链表：head <-> [1: {a, b}] <-> tail。Max=a/b, Min=a/b。
  3. inc(“b”) -> (b:2)。需要将 b 从桶1移到桶2。
    • 桶1变为 {a}。
    • 检查桶1后面是否有桶2？没有。
    • 在桶1后创建新桶2，加入 {b}。
    • 链表：head <-> [1: {a}] <-> [2: {b}] <-> tail。Max=b, Min=a。
  4. getMaxKey() -> 返回 ”b”。
  5. getMinKey() -> 返回 ”a”。
  6. dec(“a”) -> (a:0)。将 a 从桶1移除。
    • 桶1变空，删除桶1。
    • 链表：head <-> [2: {b}] <-> tail。Max=b, Min=b。
  7. getMinKey() -> 返回 ”b”。

通过这种 “哈希表 + 双向链表 + 计数桶” 的复合数据结构，我们巧妙地平衡了键值访问和极值查询的需求，使得所有操作都能在常数时间内完成。这个设计是LFU（最不经常使用）缓存算法的核心组件之一。

好的，我们随机选择一个哈希算法领域尚未讲过的题目。根据你的历史列表， “全 O(1) 的数据结构” 这个经典题目尚未被详细讲解过。 题目：全 O(1) 的数据结构 题目描述： 请你设计一个数据结构，用于高效地存储字符串键及其对应的计数值（非负整数），并支持所有操作在 常数平均时间复杂度 O(1) 内完成。需要支持以下四种操作： inc(String key) ：将键 key 的计数增加 1。如果 key 不存在，则插入其初始计数为 1。 dec(String key) ：将键 key 的计数减少 1。如果 key 的计数在减少后变为 0，则从数据结构中移除该键。如果 key 不存在，此函数不做任何操作。 getMaxKey() ：返回当前计数 最大 的任意一个键。如果数据结构为空，返回空字符串 "" 。 getMinKey() ：返回当前计数 最小 的任意一个键。如果数据结构为空，返回空字符串 "" 。 核心挑战： 既要支持键到值的快速查找和修改（这可以通过哈希表实现），又要支持在修改计数值后，能迅速找到新的最大值和最小值。而简单地维护一个最大值和最小值变量是不行的，因为当这个唯一的最大/最小值被 dec 操作后，我们需要找到“次大/次小”的值。 解题思路与过程详解 这个问题的关键在于 将相同计数的键组织在一起 ，并维护一个按计数 严格递增 的链表。链表的每个节点代表一个“计数桶”，桶内存储所有计数值相同的键。 第一步：数据结构设计 我们需要三个核心组件： 哈希表 keyMap ：键 String -> 节点 Node 。用于通过键快速定位到它当前所在的计数桶节点。 双向链表 Node ：链表节点代表一个计数值 count 。节点内包含： count : 该桶的计数值。 keys : 一个哈希集合（如 HashSet<String> ），存储所有计数值为 count 的键。 prev , next : 指向前驱和后继节点的指针。 链表的虚拟头尾节点 ：为了方便插入和删除操作，我们初始化一个双向链表，包含一个 head （计数为0的虚拟最小节点）和一个 tail （计数为0的虚拟最大节点）。 为什么是双向链表？ 因为计数的变化是相邻的（+1或-1）。当某个键的计数从 c 变为 c+1 时，它需要从代表 c 的桶移动到代表 c+1 的桶。如果 c+1 的桶不存在，我们需要在链表中 c 桶的后面 插入 一个新的桶。双向链表可以让我们在 O(1) 时间内完成节点的插入和删除。 链表顺序 ：链表从 head 到 tail 是严格递增的，即 head.count < node1.count < node2.count < ... < tail.count 。 初始状态 ：链表只有 head <-> tail 。 第二步：操作流程分析 我们以 inc(“hello”) 为例，假设初始 hello 不存在。 1. inc(String key) 情况A：键不存在 （ keyMap 中无此键）。 此时该键的计数应从 0 变为 1。 检查 head.next 是否是计数值为 1 的桶。 如果是，将 ”hello” 加入该桶的 keys 集合。 如果不是，在 head 和 head.next 之间 插入 一个新的计数值为 1 的桶，并将 ”hello” 加入其 keys 集合。 在 keyMap 中记录 ”hello” -> 这个新桶（节点1）。 最大值检查 ：由于我们是在链表最前面（最小值端）插入，最大值 tail.prev 不会受影响（除非之前链表为空，那么新插入的节点既是最大也是最小）。 情况B：键已存在 ，假设当前在计数值为 c 的桶 nodeC 中。 新计数应为 c+1 。 将 key 从 nodeC.keys 集合中移除。 检查 nodeC.next 是否是计数值为 c+1 的桶。 如果是，将 key 加入 nodeC.next.keys 。 如果不是，在 nodeC 和 nodeC.next 之间 插入 一个新的计数值为 c+1 的桶，并将 key 加入其 keys 集合。 更新 keyMap 中 key 的映射关系，指向这个新桶（ c+1 的桶）。 清理 ：如果移除 key 后， nodeC.keys 变为空（即没有任何键的计数是 c 了），则需要将 nodeC 从链表中 删除 。 最大值检查 ：如果 nodeC 恰好是原来的最大桶（ tail.prev ），并且我们创建了一个 c+1 的新桶，那么这个新桶就成为了新的最大桶。 2. dec(String key) 思路与 inc 对称，但方向相反。 如果键不存在，直接返回。 找到键所在的桶 nodeC （计数为 c ）。 将 key 从 nodeC.keys 中移除。 如果 c == 1 ，递减后计数为0，直接从 keyMap 中删除此键。 如果 c > 1 ，新计数为 c-1 。 检查 nodeC.prev 是否是计数值为 c-1 的桶。 如果是，将 key 加入 nodeC.prev.keys 。 如果不是，在 nodeC.prev 和 nodeC 之间 插入 一个新的计数值为 c-1 的桶，并将 key 加入。 更新 keyMap 。 清理 ：同样，如果移除 key 后 nodeC.keys 为空，则将 nodeC 从链表中删除。 最小值检查 ：如果 nodeC 恰好是原来的最小桶（ head.next ），并且我们创建了一个 c-1 的新桶，那么这个新桶就成为了新的最小桶。 3. getMaxKey() 与 getMinKey() 这两个操作变得非常简单。 getMaxKey() ：如果链表有效（ head.next != tail ），则返回 tail.prev.keys 集合中的 任意一个 元素（例如用迭代器的 .next() ）。 getMinKey() ：如果链表有效，则返回 head.next.keys 集合中的 任意一个 元素。 第三步：关键点与复杂度分析 为什么是 O(1) 时间？ keyMap 的查找、插入、删除是 O(1) 平均。 链表中节点的插入（在已知位置后）、删除是 O(1)。 从一个 HashSet 中增删一个元素是 O(1) 平均。 因此， inc 和 dec 的所有步骤都是常数时间操作。 getMaxKey 和 getMinKey 是直接访问，也是 O(1)。 边界情况处理 ： 空数据结构 ： head.next == tail 。此时 getMaxKey 和 getMinKey 应返回 ”” 。 计数桶为空 ：当一个桶的 keys 集合变空时， 必须 将其从链表中删除，否则会干扰 getMaxKey / getMinKey 的正确性，并造成内存泄漏。 从1减到0 ： dec 操作使计数变为0时，键应从 keyMap 中移除，且 不需要 创建计数为0的新桶（我们的虚拟 head 就是计数0的桶，但它不存储实际键）。 第四步：示例推演 假设我们依次执行： inc(“a”) -> (a:1)。链表：head <-> [ 1: {a}] <-> tail。Max=a, Min=a。 inc(“b”) -> (b:1)。链表：head <-> [ 1: {a, b}] <-> tail。Max=a/b, Min=a/b。 inc(“b”) -> (b:2)。需要将 b 从桶1移到桶2。 桶1变为 {a} 。 检查桶1后面是否有桶2？没有。 在桶1后创建新桶2，加入 {b} 。 链表：head <-> [ 1: {a}] <-> [ 2: {b}] <-> tail。Max=b, Min=a。 getMaxKey() -> 返回 ”b” 。 getMinKey() -> 返回 ”a” 。 dec(“a”) -> (a:0)。将 a 从桶1移除。 桶1变空，删除桶1。 链表：head <-> [ 2: {b}] <-> tail。Max=b, Min=b。 getMinKey() -> 返回 ”b” 。 通过这种 “哈希表 + 双向链表 + 计数桶” 的复合数据结构，我们巧妙地平衡了键值访问和极值查询的需求，使得所有操作都能在常数时间内完成。这个设计是LFU（最不经常使用）缓存算法的核心组件之一。