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

1. 题目描述

设计一个数据结构，需要支持以下操作：

• insert(val)：插入一个整数 val 到结构中；
• remove(val)：从结构中删除一个整数 val（假设 val 一定存在）；
• getMin()：返回当前所有元素中的最小值；
• getMax()：返回当前所有元素中的最大值；
• getMedian()：返回当前所有元素的中位数。

如果元素个数 n 是奇数，中位数是排序后第 (n+1)/2 小的数；如果 n 是偶数，中位数是排序后第 n/2 小的数（也可以定义成第 n/2+1 小的，但题目这里明确为“第 n/2 小的”，下面我会按这个定义实现）。

要求尽量让所有操作的时间复杂度接近 O(1) 或 O(log n)。

2. 思路分析

如果只用哈希表，可以 O(1) 插入、删除，但无法快速得到最小值、最大值和中位数，因为哈希表是无序的。
要想快速得到最值，很容易想到用堆（优先队列），但堆不支持 O(log n) 删除任意值（除非用额外的哈希表定位 + 惰性删除）。
中位数则需要有序结构支持按排名查询，常用平衡二叉搜索树（如 AVL、红黑树）或双堆（但双堆删除任意值也很麻烦）。

综合考虑：

• 用平衡二叉搜索树（如 C++ 的 multiset，Java 的 TreeMap 或手写 AVL 树）存储所有元素，保持有序，可以 O(log n) 得到最值和中位数；
• 用哈希表（字典）存储元素值 → 在平衡树中的节点引用（或者存储该值的出现次数），以便 O(1) 判断元素是否存在，并且配合平衡树实现 O(log n) 删除。

这里假设元素可重复，所以平衡树要能存储重复值（比如用 TreeMap<值, 出现次数> 或 multiset）。

3. 结构设计

我们可以用以下组合：

1. 哈希表 countMap：HashMap<val, freq> 记录每个值的出现次数。
2. 有序结构 sorted：这里用平衡二叉搜索树的“扩展”来支持按排名查询。
   在真实代码中，可以选择 C++ 的 multiset（基于红黑树），它支持插入、删除任意值 O(log n)，且可 O(1) 访问最小/最大值（通过 begin() 和 rbegin()），但取中位数需要移动迭代器到中间位置，O(n) 时间。
   若要 O(log n) 取中位数，需要额外维护树节点的大小（size）属性，以便按排名查询（即顺序统计树 Order Statistic Tree）。

4. 详细实现方案（基于两个 multiset 模拟双堆 + 哈希计数）

但更常见的做法是用两个 multiset（可重复的平衡树）模拟双堆，并额外维护一个哈希计数，这样可以在 O(log n) 时间内插入、删除、取最小、最大、中位数。

具体步骤：

• 用两个 multiset：left（存较小的一半，允许重复）、right（存较大的一半，允许重复）。
• 规定：
  • 当元素总个数 n 为偶数时，left 和 right 个数相等（均为 n/2）；
  • 当 n 为奇数时，left 比 right 多一个。
  • 这样中位数总是 left 中的最大值（即 *left.rbegin()）。
• 维护哈希表 countMap 记录每个值的出现次数，方便删除时判断。
• 插入时：
  1. 先根据 left 和 right 的大小关系以及新值的大小，决定插入哪个 multiset。
  2. 插入后调整，使得 left 的最大值 <= right 的最小值，且长度满足上述规定。
• 删除时：
  1. 从 countMap 中减少计数，如果计数归零则从哈希表删除。
  2. 判断这个值应该在 left 还是 right 中（通过比较值和 left 的最大值的大小关系），然后从对应的 multiset 删除。
  3. 调整两个 multiset 的大小平衡。
• getMin：整个结构的最小值 = left 的最小值（即 *left.begin()）。
• getMax：整个结构的最大值 = right 的最大值（即 *right.rbegin()），如果 right 为空则取 left 的最大值。
• getMedian：即 left 的最大值（*left.rbegin()）。

5. 操作过程示例

初始

left = {}, right = {}, n=0, countMap={}

插入 5

n=1，插入到 left，left={5}, right={}
中位数是 5，最小值 5，最大值 5。

插入 8

比较 8 和 left 最大值 5，8 较大，应插入 right。
插入后 left={5}, right={8}，n=2 偶数，左右大小相等，满足。
调整：left 最大值 5 ≤ right 最小值 8，已满足。
中位数是 left 的最大值 5，最小值 5，最大值 8。

插入 2

比较 2 和 left 最大值 5，2 较小，应插入 left。
插入后 left={2,5}, right={8}，n=3 奇数，left 应比 right 多 1，现在 left 有 2，right 有 1，满足。
调整：left 最大值 5 ≤ right 最小值 8，满足。
中位数是 5，最小值 2，最大值 8。

插入 5

countMap[5]++ 变为 2。
比较 5 和 left 最大值 5，相等，插入 left。
插入后 left={2,5,5}, right={8}，n=4 偶数，左右应相等，现在 left 有 3，right 有 1，不满足，需要从 left 移动一个最大元素到 right。
移动 5 到 right，left={2,5}, right={5,8}。
中位数是 left 的最大值 5，最小值 2，最大值 8。

6. 时间复杂度分析

• 插入：O(log n)（multiset 插入、查找最大最小值 O(1)、移动元素 O(log n)）
• 删除：O(log n)（需要先定位在哪个 multiset，然后删除，再平衡）
• getMin、getMax、getMedian：O(1)（通过 multiset 的 begin、rbegin 直接访问）

7. 伪代码实现（基于 C++ multiset 思路）

#include <unordered_map>
#include <set>
using namespace std;

class MedianStructure {
private:
    multiset<int> left, right; // left 存较小的一半，right 存较大的一半
    unordered_map<int, int> countMap;
    
    // 保持 left.size() == right.size() 或 left.size() == right.size() + 1
    void rebalance() {
        while (left.size() > right.size() + 1) {
            auto it = prev(left.end());
            right.insert(*it);
            left.erase(it);
        }
        while (right.size() > left.size()) {
            auto it = right.begin();
            left.insert(*it);
            right.erase(it);
        }
    }
    
public:
    void insert(int val) {
        countMap[val]++;
        if (left.empty() || val <= *left.rbegin()) {
            left.insert(val);
        } else {
            right.insert(val);
        }
        rebalance();
    }
    
    void remove(int val) {
        if (!countMap.count(val)) return;
        countMap[val]--;
        if (countMap[val] == 0) countMap.erase(val);
        
        // 从 left 或 right 中删除一个 val
        auto it = left.find(val);
        if (it != left.end()) {
            left.erase(it);
        } else {
            it = right.find(val);
            right.erase(it);
        }
        rebalance();
    }
    
    int getMin() {
        if (left.empty()) return -1; // 假设无元素返回 -1
        return *left.begin();
    }
    
    int getMax() {
        if (right.empty()) {
            if (left.empty()) return -1;
            return *left.rbegin();
        }
        return *right.rbegin();
    }
    
    int getMedian() {
        if (left.empty()) return -1;
        return *left.rbegin();
    }
};

8. 总结

这个结构结合了哈希表（用于计数和存在性判断）与平衡树（用于维护有序性和中位数查询），实现了所有操作在 O(log n) 时间内完成，而获取最小值、最大值和中位数只需 O(1) 时间。