哈希算法题目：全 O(1) 的数据结构
字数 2965 2025-10-28 11:34:06

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

题目描述

请你设计一个数据结构，用于存储字符串及其计数的键值对。这个数据结构需要支持以下四种操作，并且每种操作的平均时间复杂度都需要是 O(1)：

  1. inc(String key)：

    • 如果 key 在数据结构中不存在，则插入这个 key，并将它的计数设置为 1。
    • 如果 key 已经存在，则将其对应的计数增加 1。

  2. dec(String key)：

    • 如果 key 的计数为 1，则在数据结构中移除这个 key。
    • 如果 key 的计数大于 1，则将其对应的计数减少 1。
    • 如果 key 不存在，该函数不做任何操作。

  3. getMaxKey()：返回任意一个计数最大的 key。如果数据结构为空，返回空字符串 ""。

  4. getMinKey()：返回任意一个计数最小的 key。如果数据结构为空，返回空字符串 ""。

解题过程

这个题目的难点在于，我们不仅要能快速（O(1)）地通过 key 找到其对应的计数（这可以用哈希表轻松实现），还要能快速（O(1)）地找到全局的最大计数和最小计数，并从中返回一个 key。

如果我们只用一个哈希表（key -> count），那么 inc 和 dec 操作可以是 O(1)，但 getMaxKey 和 getMinKey 就需要遍历整个哈希表，时间复杂度是 O(n)，不符合要求。

因此，我们需要一个更精巧的设计。核心思路是使用 哈希表 + 双向链表。

  1. 设计节点（Node）：表示一个计数桶
    我们把具有相同计数的所有 key 放在一个“桶”里。这个桶就是一个节点。每个节点需要存储：

    • count：这个桶代表的计数值。
    • keys：一个集合（例如 HashSet），存储所有计数为 count 的 key。使用 HashSet 可以让我们在 O(1) 时间内添加或删除一个 key。
    • prev：指向前一个节点的指针。
    • next：指向后一个节点的指针。

    为什么用双向链表？因为当某个 key 的计数增加或减少时，它需要从一个桶（节点）移动到相邻的另一个桶（计数+1或-1的节点）。双向链表可以让我们在 O(1) 时间内完成节点的插入和删除。

  2. 设计整体数据结构

    • keyMap：一个哈希表，映射是 key -> Node。通过它，我们可以根据一个 key 快速找到它目前所在的节点（桶）。
    • countList：一个双向链表，链表中的每个节点都是一个我们上面描述的“计数桶”。为了便于操作，我们设置两个哨兵节点：head（虚拟头节点）和 tail（虚拟尾节点）。链表从 head 到 tail，节点的 count 值依次递增。这样，head.next 就是计数最小的节点，tail.prev 就是计数最大的节点。

  3. 操作步骤详解

    • 初始化
      创建 keyMap 和一个空的双向链表，链表只有 head 和 tail 两个节点，它们相互连接。

    • inc(String key) 操作

      1. 检查 key 是否在 keyMap 中。
        • 如果不存在：
          • 检查 head 的下一个节点（即最小计数节点）的计数值是否为 1。
          • 如果是，说明已经有计数为 1 的桶，直接将这个 key 加入该节点的 keys 集合中。
          • 如果不是，说明还没有计数为 1 的桶。我们需要在 head 后面创建一个新的节点（count=1），并将 key 加入这个新节点的 keys 集合中。
          • 最后，在 keyMap 中建立 key 到这个（计数为1的）节点的映射。
        • 如果存在：
          • 通过 keyMap 找到 key 当前所在的节点 oldNode，其计数为 c。
          • 从 oldNode.keys 集合中移除这个 key。
          • 检查 oldNode 的下一个节点 nextNode 的计数值是否为 c+1。
            • 如果是，说明已经有计数为 c+1 的桶，直接将这个 key 加入 nextNode.keys 集合中。并更新 keyMap 的映射为 key -> nextNode。
            • 如果不是，说明还没有计数为 c+1 的桶。我们需要在 oldNode 和 nextNode 之间创建一个新的节点（count = c+1），并将 key 加入这个新节点的 keys 集合中。并更新 keyMap。
          • 关键步骤：如果 oldNode.keys 在移除 key 后变成了空集合，这意味着这个计数桶已经没有任何 key 了。我们需要将这个空的 oldNode 从双向链表中删除，以保持链表的整洁。

    • dec(String key) 操作（与 inc 对称）

      1. 检查 key 是否在 keyMap 中。如果不存在，直接返回。
      2. 通过 keyMap 找到 key 当前所在的节点 oldNode，其计数为 c。
      3. 从 oldNode.keys 集合中移除这个 key。
      4. 如果 c == 1：
        • 直接从 keyMap 中移除这个 key 的映射。
      5. 如果 c > 1：
        • 检查 oldNode 的前一个节点 prevNode 的计数值是否为 c-1。
          • 如果是，将 key 加入 prevNode.keys 集合，并更新 keyMap。
          • 如果不是，在 prevNode 和 oldNode 之间创建一个新的节点（count = c-1），加入 key，并更新 keyMap。
      6. 关键步骤：同样，如果 oldNode.keys 在移除 key 后变成了空集合，我们将这个空的 oldNode 从链表中删除。

    • getMaxKey() 操作

      • 我们的链表是有序的，最大计数的节点是 tail 的前一个节点 tail.prev。
      • 如果 tail.prev 是 head，说明链表是空的（只有哨兵节点），返回空字符串 ""。
      • 否则，从 tail.prev.keys 这个集合中任意返回一个 key（例如，用迭代器返回第一个）。

    • getMinKey() 操作

      • 最小计数的节点是 head 的后一个节点 head.next。
      • 如果 head.next 是 tail，说明链表是空的，返回空字符串 ""。
      • 否则，从 head.next.keys 这个集合中任意返回一个 key。

总结

通过结合哈希表（keyMap）和双向链表（countList），我们为每个出现的计数值维护了一个“桶”。哈希表保证了我们能用 O(1) 的时间访问到任何一个 key 所在的桶。双向链表保证了所有桶按计数值有序排列，并且当计数变化时，key 可以在相邻的桶之间快速移动。哨兵节点的使用简化了边界条件（如链表为空）的处理。这样，我们就成功地实现了所有四种操作都是 O(1) 时间复杂度的数据结构。

哈希算法题目：全 O(1) 的数据结构 题目描述 请你设计一个数据结构，用于存储字符串及其计数的键值对。这个数据结构需要支持以下四种操作，并且每种操作的平均时间复杂度都需要是 O(1)： inc(String key) ： 如果 key 在数据结构中不存在，则插入这个 key ，并将它的计数设置为 1。 如果 key 已经存在，则将其对应的计数增加 1。 dec(String key) ： 如果 key 的计数为 1，则在数据结构中移除这个 key 。 如果 key 的计数大于 1，则将其对应的计数减少 1。 如果 key 不存在，该函数不做任何操作。 getMaxKey() ：返回任意一个计数最大的 key 。如果数据结构为空，返回空字符串 "" 。 getMinKey() ：返回任意一个计数最小的 key 。如果数据结构为空，返回空字符串 "" 。 解题过程 这个题目的难点在于，我们不仅要能快速（O(1)）地通过 key 找到其对应的计数（这可以用哈希表轻松实现），还要能快速（O(1)）地找到全局的最大计数和最小计数，并从中返回一个 key 。 如果我们只用一个哈希表（ key -> count ），那么 inc 和 dec 操作可以是 O(1)，但 getMaxKey 和 getMinKey 就需要遍历整个哈希表，时间复杂度是 O(n)，不符合要求。 因此，我们需要一个更精巧的设计。核心思路是使用 哈希表 + 双向链表 。 设计节点（Node）：表示一个计数桶 我们把具有相同计数的所有 key 放在一个“桶”里。这个桶就是一个节点。每个节点需要存储： count ：这个桶代表的计数值。 keys ：一个集合（例如 HashSet ），存储所有计数为 count 的 key 。使用 HashSet 可以让我们在 O(1) 时间内添加或删除一个 key 。 prev ：指向前一个节点的指针。 next ：指向后一个节点的指针。 为什么用双向链表？因为当某个 key 的计数增加或减少时，它需要从一个桶（节点）移动到相邻的另一个桶（计数+1或-1的节点）。双向链表可以让我们在 O(1) 时间内完成节点的插入和删除。 设计整体数据结构 keyMap ：一个哈希表，映射是 key -> Node 。通过它，我们可以根据一个 key 快速找到它目前所在的节点（桶）。 countList ：一个双向链表，链表中的每个节点都是一个我们上面描述的“计数桶”。为了便于操作，我们设置两个哨兵节点： head （虚拟头节点）和 tail （虚拟尾节点）。链表从 head 到 tail ，节点的 count 值依次递增。这样， head.next 就是计数最小的节点， tail.prev 就是计数最大的节点。 操作步骤详解 初始化 创建 keyMap 和一个空的双向链表，链表只有 head 和 tail 两个节点，它们相互连接。 inc(String key) 操作 检查 key 是否在 keyMap 中。 如果不存在 ： 检查 head 的下一个节点（即最小计数节点）的计数值是否为 1。 如果是，说明已经有计数为 1 的桶，直接将这个 key 加入该节点的 keys 集合中。 如果不是，说明还没有计数为 1 的桶。我们需要在 head 后面创建一个新的节点（ count=1 ），并将 key 加入这个新节点的 keys 集合中。 最后，在 keyMap 中建立 key 到这个（计数为1的）节点的映射。 如果存在 ： 通过 keyMap 找到 key 当前所在的节点 oldNode ，其计数为 c 。 从 oldNode.keys 集合中移除这个 key 。 检查 oldNode 的下一个节点 nextNode 的计数值是否为 c+1 。 如果是，说明已经有计数为 c+1 的桶，直接将这个 key 加入 nextNode.keys 集合中。并更新 keyMap 的映射为 key -> nextNode 。 如果不是，说明还没有计数为 c+1 的桶。我们需要在 oldNode 和 nextNode 之间创建一个新的节点（ count = c+1 ），并将 key 加入这个新节点的 keys 集合中。并更新 keyMap 。 关键步骤 ：如果 oldNode.keys 在移除 key 后变成了空集合，这意味着这个计数桶已经没有任何 key 了。我们需要将这个空的 oldNode 从双向链表中删除，以保持链表的整洁。 dec(String key) 操作（与 inc 对称） 检查 key 是否在 keyMap 中。如果不存在，直接返回。 通过 keyMap 找到 key 当前所在的节点 oldNode ，其计数为 c 。 从 oldNode.keys 集合中移除这个 key 。 如果 c == 1 ： 直接从 keyMap 中移除这个 key 的映射。 如果 c > 1 ： 检查 oldNode 的前一个节点 prevNode 的计数值是否为 c-1 。 如果是，将 key 加入 prevNode.keys 集合，并更新 keyMap 。 如果不是，在 prevNode 和 oldNode 之间创建一个新的节点（ count = c-1 ），加入 key ，并更新 keyMap 。 关键步骤 ：同样，如果 oldNode.keys 在移除 key 后变成了空集合，我们将这个空的 oldNode 从链表中删除。 getMaxKey() 操作 我们的链表是有序的，最大计数的节点是 tail 的前一个节点 tail.prev 。 如果 tail.prev 是 head ，说明链表是空的（只有哨兵节点），返回空字符串 "" 。 否则，从 tail.prev.keys 这个集合中任意返回一个 key （例如，用迭代器返回第一个）。 getMinKey() 操作 最小计数的节点是 head 的后一个节点 head.next 。 如果 head.next 是 tail ，说明链表是空的，返回空字符串 "" 。 否则，从 head.next.keys 这个集合中任意返回一个 key 。 总结 通过结合哈希表（ keyMap ）和双向链表（ countList ），我们为每个出现的计数值维护了一个“桶”。哈希表保证了我们能用 O(1) 的时间访问到任何一个 key 所在的桶。双向链表保证了所有桶按计数值有序排列，并且当计数变化时， key 可以在相邻的桶之间快速移动。哨兵节点的使用简化了边界条件（如链表为空）的处理。这样，我们就成功地实现了所有四种操作都是 O(1) 时间复杂度的数据结构。