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

题目描述

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

1. insert(val)：插入元素 val。
2. remove(val)：删除元素 val（假设一定存在）。
3. getMin()：返回最小值。
4. getMax()：返回最大值。
5. getMedian()：返回中位数（若元素数为偶数，取中间两个数的平均值）。

要求所有操作的时间复杂度尽可能低（理想情况下接近 O(1)）。

解题思路

单纯使用哈希表（如 unordered_map）只能实现 O(1) 的插入和删除，但无法快速获取中位数。而中位数需要维护元素的有序性，通常需要 O(log n) 时间（如用平衡树或堆）。为了兼顾快速查找极值和中位数，需结合多种数据结构：

1. 哈希表：记录每个值的出现次数，支持 O(1) 时间验证元素是否存在。
2. 双堆（最小堆+最大堆）：维护中位数，但堆不支持 O(1) 删除任意元素。
3. 平衡树（如红黑树）：天然有序，支持 O(log n) 插入、删除、查找极值和中位数，但无法达到 O(1) 时间复杂度。

若要求所有操作接近 O(1)，需采用更复杂的结构：双向链表+哈希表（类似 LFU 缓存的设计），但中位数仍需遍历。因此，实际方案需在时间复杂度和实现复杂度之间权衡。

渐进实现步骤

步骤 1：选择核心数据结构

采用 两个多重集合（multiset） 或 平衡树 维护有序元素，并用哈希表记录元素频次（处理重复值）：

• 用 multiset<int> 存储元素，自动排序，支持 O(log n) 插入、删除、查找极值。
• 用 unordered_map<int, int> 记录每个值的出现次数，避免重复插入相同值到 multiset。
• 中位数通过指针或迭代器定位：维护一个指向中位数的迭代器，插入或删除时动态调整。

步骤 2：维护中位数的迭代器

1. 初始化空集合和指向结束的迭代器 mid。
2. 插入元素时：
   • 若集合为空，直接插入并让 mid 指向唯一元素。
   • 若新元素小于或等于 *mid，且当前元素数为奇数，则 mid 前移；若为偶数，保持不动。
3. 删除元素时：
   • 若删除的元素小于或等于 *mid，且当前元素数为奇数，则 mid 后移；若为偶数，保持不动。
4. 通过 *mid 或前后元素平均值计算中位数。

步骤 3：处理重复值

哈希表 freq 记录每个值的频次：

• 插入 val 时：若 freq[val] == 0，才将 val 加入 multiset；否则仅增加频次。
• 删除 val 时：减少频次，若 freq[val] == 0，才从 multiset 删除。

步骤 4：获取极值

直接通过 multiset 的首尾迭代器获取最小值和最大值（O(1) 时间）。

代码实现示例（C++）

#include <unordered_map>
#include <set>
class MedianStructure {
private:
    std::multiset<int> nums;
    std::unordered_map<int, int> freq;
    std::multiset<int>::iterator mid; // 指向中位数或偏右位置
public:
    MedianStructure() : mid(nums.end()) {}

    void insert(int val) {
        // 处理重复值
        if (freq[val] == 0) {
            nums.insert(val);
            // 调整中位数指针
            if (nums.size() == 1) {
                mid = nums.begin();
            } else if (val <= *mid) {
                // 新元素在mid左侧，若原大小为奇数则mid左移
                mid = (nums.size() % 2 == 1) ? std::prev(mid) : mid;
            } else {
                // 新元素在mid右侧，若原大小为偶数则mid右移
                mid = (nums.size() % 2 == 0) ? std::next(mid) : mid;
            }
        }
        freq[val]++;
    }

    void remove(int val) {
        if (freq[val] == 0) return;
        freq[val]--;
        if (freq[val] > 0) return; // 仍有重复值，不删除集合中的元素

        auto it = nums.find(val);
        bool left = (val <= *mid); // 删除元素是否在mid左侧
        if (it == mid) {
            // 删除的是mid指向的元素
            mid = (nums.size() % 2 == 0) ? std::next(mid) : std::prev(mid);
        } else if (left) {
            // 删除左侧元素，若原大小为偶数则mid右移
            mid = (nums.size() % 2 == 0) ? std::next(mid) : mid;
        } else {
            // 删除右侧元素，若原大小为奇数则mid左移
            mid = (nums.size() % 2 == 1) ? std::prev(mid) : mid;
        }
        nums.erase(it);
    }

    int getMin() { return *nums.begin(); }
    int getMax() { return *nums.rbegin(); }
    double getMedian() {
        if (nums.size() % 2 == 1) return *mid;
        auto prev_mid = std::prev(mid);
        return (*prev_mid + *mid) / 2.0;
    }
};

复杂度分析

• 插入/删除：平均 O(log n)，因 multiset 基于平衡树。
• 极值查询：O(1)。
• 中位数查询：O(1)。
• 空间复杂度：O(n)。

此方案在有序性和操作效率之间取得了平衡，适用于需要频繁查询中位数和极值的场景。