设计一个支持快速查找最小值、最大值、中位数的哈希结构

题目描述
设计一个数据结构，支持以下操作：

1. insert(val)：将一个整数 val 插入数据结构中。
2. remove(val)：将一个整数 val 从数据结构中删除（假设 val 一定存在）。
3. getMin()：返回当前数据结构中的最小值。
4. getMax()：返回当前数据结构中的最大值。
5. getMedian()：返回当前数据结构的中位数。如果当前元素个数 n 是奇数，中位数是排序后第 (n+1)/2 小的数；如果是偶数，中位数是排序后第 n/2 小的数（或第 n/2 和 n/2+1 的平均值，这里我们约定取第 n/2 小的数）。

要求所有操作的平均时间复杂度尽可能低，并利用哈希表（散列表）来优化某些操作的性能。

解题思路
这个问题的难点在于要同时支持多种统计查询（最小值、最大值、中位数），而且还要支持插入和删除。如果单纯用一个数组，插入和删除是 O(1)（如果无序），但查找最小值、最大值、中位数需要 O(n) 扫描或排序。如果用一个有序数组，插入和删除是 O(n)（因为要移动元素），但查询中位数是 O(1)（直接用索引访问）。我们需要一种混合策略，在多种操作间取得平衡。

核心思路：

1. 用两个哈希表来分别记录每个值的出现次数，以及当前数据结构中所有值的有序统计信息。
2. 一个哈希表 freq 用来记录每个值出现的频率，这样可以支持 O(1) 的插入和删除（如果只是频率增减）。
3. 同时，用一个平衡的、支持重复值的、可快速查找第 k 小元素的数据结构来维护所有数字的顺序，比如 两个优先队列（堆） 或 平衡二叉搜索树（如红黑树）。这里我们选择 两个堆 + 哈希表延迟删除 的方法来实现 O(log n) 的插入/删除和 O(1) 的查询最小值、最大值、中位数。但为了更直观，我们采用 平衡二叉搜索树（SortedList） 的思路，并用哈希表来优化重复值的存储。
4. 实际上，我们可以用标准库中的 有序容器（如 C++ 的 multiset 或 Python 的 SortedList）来维护有序集合，再用一个哈希表 freq 来记录每个值的出现次数，以保证删除时能正确处理重复值。

具体步骤分解：

步骤 1：数据结构设计
我们维护以下两个核心部分：

• SortedList：一个有序列表，支持快速插入、删除、按索引访问（从而可快速获取最小值、最大值、中位数）。在 Python 中，可以用 SortedList 从 sortedcontainers 库（面试时可以说“假设有现成有序列表数据结构”），或者自己用平衡二叉搜索树实现。
• Counter（哈希表）：一个从值到其出现次数的映射，键是整数，值是频率。

为什么需要两个？
因为如果只用 SortedList，当有重复值时，删除一个值需要知道删除哪一个实例。通过 Counter 我们可以知道某个值是否还存在，以及还有几个。当我们删除一个值 val 时，先从 Counter 中减少其频率，如果频率减到 0，则从 SortedList 中删除这个值的一次出现（删除一个实例）。这样保证 SortedList 中每个值出现的次数和 Counter 一致。

步骤 2：操作实现

1. insert(val)：

   • 将 val 的频率加 1（哈希表操作，O(1)）。
   • 如果加 1 后频率为 1（说明这个值原先不存在），则把 val 插入到 SortedList 中（O(log n)）。
   • 如果频率大于 1（说明这个值已存在于 SortedList 中），则无需重复插入，因为 SortedList 可以存储重复值（如果实现支持的话）。在 Python 的 SortedList 中，重复值会自动处理，我们只需要插入一次，但我们的设计是 SortedList 存储所有独立值（不存重复），而用 Counter 记录次数。但这里为了简单，我们让 SortedList 存储每个值的单个键，并配合 Counter 来记录重复。但这样中位数计算会变复杂，所以我们选择让 SortedList 存储每个出现实例（即允许重复值）。
   • 更简单的做法：直接用 SortedList 存储所有实例（允许重复），并用 Counter 辅助验证。插入时总是向 SortedList 插入一次 val，并增加 Counter[val]。

2. remove(val)：

   • 检查 Counter[val] 是否大于 0，如果不是，说明不存在，直接返回错误（题目假设存在）。
   • 将 Counter[val] 减 1。
   • 从 SortedList 中删除一个 val 的实例（O(log n)）。
   • 如果 Counter[val] 减到 0，则从哈希表删除这个键（可选）。

3. getMin()：

   • 返回 SortedList 的第一个元素（索引 0），O(1) 或 O(log n) 取决于实现（在 SortedList 中是 O(1) 如果支持直接访问首元素）。

4. getMax()：

   • 返回 SortedList 的最后一个元素（索引 len(SortedList)-1），O(1) 或 O(log n)。

5. getMedian()：

   • 设 n = len(SortedList)。
   • 如果 n 是奇数，返回索引为 (n-1)//2 的元素。
   • 如果 n 是偶数，返回索引为 (n//2)-1 的元素（根据题意取第 n/2 小的数，索引是 n/2 - 1）。

步骤 3：复杂度分析

• 插入：O(log n)（因为要向有序列表插入）
• 删除：O(log n)（从有序列表删除）
• 查询最小值、最大值、中位数：O(1)（如果有序列表支持按索引访问）
• 空间：O(n)

步骤 4：边界条件和示例

示例：

1. 插入 1, 2, 2, 3
   • SortedList = [1, 2, 2, 3]
   • Counter = {1:1, 2:2, 3:1}
2. getMin() → 1
3. getMax() → 3
4. getMedian() → n=4，偶数，取索引 1（第 2 小的数）→ 2
5. remove(2)
   • Counter[2] 从 2 减为 1
   • 从 SortedList 删除一个 2 → SortedList = [1, 2, 3]
6. getMedian() → n=3，奇数，取索引 1 → 2

步骤 5：实现细节
如果手写，我们需要实现一个允许重复值的平衡二叉搜索树，并记录每个节点子树的大小，以支持按索引查找（类似 Order Statistic Tree）。但面试中，我们可以说明使用库的 SortedList 来简化。

伪代码（Python 风格，使用 sortedcontainers 库的 SortedList）：

from sortedcontainers import SortedList
from collections import defaultdict

class FastStatHashStructure:
    def __init__(self):
        self.sl = SortedList()  # 有序列表，存储所有值实例（允许重复）
        self.counter = defaultdict(int)  # 哈希表，值 -> 频率

    def insert(self, val):
        self.sl.add(val)
        self.counter[val] += 1

    def remove(self, val):
        if self.counter[val] == 0:
            raise ValueError(f"Value {val} not found")
        self.sl.remove(val)  # 删除一个实例
        self.counter[val] -= 1
        if self.counter[val] == 0:
            del self.counter[val]

    def getMin(self):
        return self.sl[0]

    def getMax(self):
        return self.sl[-1]

    def getMedian(self):
        n = len(self.sl)
        if n % 2 == 1:
            return self.sl[n//2]
        else:
            return self.sl[n//2 - 1]  # 第 n/2 小的数（0-indexed）

总结
这个数据结构结合了哈希表（用于快速判断存在性和频率）和有序列表（用于维护顺序），从而高效地支持插入、删除、查询最小值、最大值、中位数。哈希表在这里的关键作用是处理重复值，避免有序列表中对重复值删除的歧义，同时也保证了删除操作的正确性。这是一种典型的“哈希+有序结构”组合应用场景。