哈希算法题目：设计一个支持快速查找最小值、最大值、中位数的哈希结构 题目描述 设计一个数据结构，支持以下操作： insert(val) ：插入一个整数。 remove(val) ：删除一个整数（保证存在）。 getMin() ：返回当前最小值。 getMax() ：返回当前最大值。 getMedian() ：返回当前中位数（若元素数为偶数，取中间两个的较小值）。 要求所有操作的时间复杂度尽可能低（理想为 O(1) 或 O(log n)）。 解题思路 单纯使用哈希表无法直接支持有序统计操作（如中位数）。需要结合哈希表和有序结构： 哈希表 （ unordered_map ）：记录每个值的出现次数，用于快速验证存在性及计数。 有序结构 （如平衡树或双堆）：维护数据的有序性，以支持最小值、最大值和中位数的快速查询。 步骤分解 1. 选择核心数据结构 使用 map<int, int> （或平衡树）记录每个数值及其出现次数，同时天然保持键有序。但插入/删除为 O(log n)，获取极值 O(1)，但中位数需遍历一半键，效率低（O(n)）。 优化方案 ：用 双堆（最小堆+最大堆） 结合哈希表： 最小堆 minHeap 存储较大的一半数（堆顶为较大半的最小值）。 最大堆 maxHeap 存储较小的一半数（堆顶为较小半的最大值）。 哈希表 freq 记录每个值的出现次数，用于删除时延迟清理。 维护两堆大小平衡：保证 maxHeap 的大小等于或比 minHeap 多1，以便中位数直接取 maxHeap 堆顶。 2. 操作实现细节 插入 insert(val) ： 若 maxHeap 为空或 val ≤ maxHeap.top() ，插入 maxHeap ；否则插入 minHeap 。 调整平衡：若 maxHeap 大小比 minHeap 多2，将 maxHeap.top() 移到 minHeap ；若 minHeap 大小大于 maxHeap ，将 minHeap.top() 移到 maxHeap 。 更新 freq[val]++ 。 删除 remove(val) ： 若 freq[val] 为0，直接返回。否则 freq[val]-- 。 延迟删除：不立即从堆中移除，仅在查询极值或中位数时清理堆顶无效值。 查询操作 ： getMin() ：清理 minHeap 和 maxHeap 的无效堆顶后，返回 maxHeap.top() （因为 maxHeap 存较小半，其堆顶为全局最小）。 getMax() ：清理无效堆顶后，若 minHeap 非空则返回 minHeap.top() （较大半的最大值），否则返回 maxHeap.top() 。 getMedian() ：清理无效堆顶后，直接返回 maxHeap.top() （因维护了 maxHeap 大小总不少于 minHeap ）。 3. 延迟删除技巧 为每个堆维护一个哈希表 pending ，记录待删除值及其次数。 当堆顶值在 pending 中存在时，弹出并减少 pending 计数，直到堆顶有效。 示例演示 插入序列： [5, 3, 5, 2, 1] 插入5： maxHeap: {5} , minHeap: {} , freq: {5:1} 。 插入3： maxHeap: {3,5} , minHeap: {} → 调整后 maxHeap: {3} , minHeap: {5} 。 插入5： minHeap: {5,5} , 调整后 maxHeap: {3,5} , minHeap: {5} 。 插入2： maxHeap: {2,3,5} , minHeap: {5} → 调整后 maxHeap: {2,3} , minHeap: {5,5} 。 插入1： maxHeap: {1,2,3} , minHeap: {5,5} → 调整后 maxHeap: {1,2} , minHeap: {3,5,5} 。 查询： getMin() = 1（ maxHeap.top() ）。 getMax() = 5（ minHeap.top() ）。 getMedian() = 2（ maxHeap.top() ）。 复杂度分析 插入/删除：调整堆的复杂度 O(log n)，哈希表操作 O(1)。 查询极值/中位数：延迟删除的均摊复杂度 O(1)。 关键点 双堆平衡确保中位数直接可得。 延迟删除避免频繁堆操作，保证高效性。 哈希表维护计数，确保删除正确性。