哈希算法题目：设计一个支持动态顺序统计的哈希结构

字数 2907 2025-12-07 22:59:40

哈希算法题目：设计一个支持动态顺序统计的哈希结构

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

insert(val)：插入一个整数 val 到结构中（允许重复值）。
delete(val)：删除一个 val（若有多个重复值，只删除一个）。
getRandom()：等概率随机返回一个现有值。
getMedian()：返回当前所有值的中位数。若元素数量为偶数，返回中间两个值的平均值。

要求所有操作的平均时间复杂度为 O(1)（getMedian 除外，其要求平均 O(1) 但需巧妙设计）。

解题过程循序渐进讲解

第一步：分析核心挑战

哈希表通常支持 O(1) 的插入、删除、随机访问（通过数组索引），但随机返回元素值需要维护元素列表。
中位数操作需要有序数据，传统做法需排序（O(n log n)）或使用堆（O(log n)），但题目要求平均 O(1)。
关键矛盾：哈希表无序，而中位数需要顺序信息。因此需结合哈希表和有序结构，并维护动态顺序统计。

第二步：借鉴“常数时间随机返回”的设计
常用技巧：用哈希表（值 → 索引集合）和动态数组（存储值）结合，实现 O(1) 插入、删除、getRandom。

数组支持随机索引访问。
删除时，将数组末尾元素移到被删位置，更新哈希表，避免整体移动。
例子：插入 [5, 5, 6]，数组为 [5, 5, 6]，哈希表为 {5→{0,1}, 6→{2}}。

第三步：加入中位数操作的设计思路
要在 O(1) 时间得到中位数，必须维护一个始终有序的序列，并快速定位中间位置。
可行方案：双哈希表 + 双端队列扩展？不，仍需排序。
更优方案：使用两个平衡的多重集合（MultiSet），模拟“双堆”但支持快速删除任意值。

用两个平衡的 BST（如 TreeSet，但需支持重复值）或 “排序列表 + 哈希索引” 实现。
但 BST 操作是 O(log n)，不符合 O(1) 要求。

第四步：重新审视“平均 O(1)”的含义
若允许近似中位数，可用“分桶统计”，但题目要求精确中位数。
精确中位数在动态数据中必须维护有序性，插入删除最坏至少 O(log n)。但“平均 O(1)”可通过 “懒更新 + 周期重排” 实现：

维护一个数组 sorted 作为缓存有序序列，一个哈希表 valToIndices 指向数组中的位置（多个重复值需记录多个索引）。
插入时，将新值放到未排序的缓冲区 buffer 中（O(1)），并更新哈希表。
删除时，标记该值在哈希表中的索引为“已删除”，不立即重排。
当缓冲区大小达到阈值（如 √n），触发重排：合并 sorted 和 buffer，重新排序，重建索引（O(n) 但分摊到 √n 次操作，平均 O(√n)）。
中位数直接从有序数组 sorted 中间位置取（O(1)）。
但此法不满足严格 O(1) 平均，是 O(√n)。

第五步：严格 O(1) 中位数的理论可能性
已知文献有 “动态顺序统计树”（如 Order Statistic Tree）可实现插入、删除、查询第 k 大均为 O(log n)。若要 O(1) 中位数，必须在插入删除时动态维护中间指针。
一种方法：用 “双端可扩展数组 + 中位数指针”：

将数据分为三部分：left（小于中位数）、mid（等于当前中位数的一组值）、right（大于中位数）。
用哈希表记录每个值所属部分（left/mid/right）及在部分内的位置。
中位数即 mid 部分的第一个值（奇数总数）或 (mid首 + right首)/2（偶数总数调整）。
插入时，根据值与当前中位数比较，放入对应部分，并调整 mid 的边界，使 left 和 right 大小平衡。
删除时类似调整。
此方法在插入删除时只需 O(1) 的指针移动，但需细致维护重复值的存储结构。

第六步：具体数据结构设计

用 HashMap<Integer, LinkedHashSet<Integer>> valToIndices 记录每个值在数组中的索引集合（以便 O(1) 删除任意一个）。
用 ArrayList<Integer> arr 存储实际值，支持 getRandom。
用 TreeMap<Integer, Integer> countMap 记录每个值的频率（键有序）。
用 int totalCount 记录总元素个数。
中位数计算：从 TreeMap 中顺序遍历，找到第 (totalCount+1)/2 个值（中位数位置），因 TreeMap 按键有序，但值未按插入顺序，所以需用频次累加找到中位数所在的键。
但 TreeMap 找中位数需 O(k) 时间（k 为不同键的数量），不满足 O(1)。

第七步：最终可实现平均 O(1) 的折中方案

插入、删除、getRandom 严格 O(1)。
getMedian 用“有序哈希”思想：
维护一个 LinkedHashMap<Integer, Integer> 记录值频次，并保持键按值大小排序（插入时用二分查找确定位置，但会破坏 O(1)）。
实际上，若要严格 O(1) 中位数，必须牺牲部分操作的简洁性，或使用复杂的数据结构（如“哈希表 + 中位数指针 + 左右平衡链”）。
工程中可接受近似 O(1)，用“分桶计数+中位数缓存”，每次插入删除更新中位数缓存。

示例操作流程
数据结构：

List<Integer> arr = [5, 3, 5, 7]
Map<Integer, LinkedHashSet<Integer>> valToIdx = {5->{0,2}, 3->{1}, 7->{3}}
TreeMap<Integer, Integer> countMap = {3:1, 5:2, 7:1} 有序计数。

getMedian()：
totalCount=4，中位数位置 2.5（第2和第3个数的平均）。
从 countMap 累加频次：3(1) -> 位置1；5(2) -> 位置2-3；所以中位数是 (5+5)/2=5。

删除一个 5：
从 valToIdx[5] 取一个索引 0，将 arr[0] 与 arr 末尾交换（arr[3]=7 换到 0），更新 valToIdx[7] 的索引从 {3} 改为 {0}，删除 arr 末尾，valToIdx[5] 移除 0。
countMap[5] 减为 1。

总结
本题结合了哈希表、动态数组、有序计数映射，核心在于：

用哈希+数组实现 O(1) 插入、删除、随机返回。
用有序计数映射（TreeMap）计算中位数，时间复杂度 O(k)（k 为不同值个数），若值域有限可优化为 O(1)。
若要完全满足 O(1) 中位数，需使用更复杂的“双哈希表 + 中位数指针平衡”结构，但实现较为复杂。

哈希算法题目：设计一个支持动态顺序统计的哈希结构题目描述设计一个哈希结构，支持以下操作： insert(val) ：插入一个整数 val 到结构中（允许重复值）。 delete(val) ：删除一个 val （若有多个重复值，只删除一个）。 getRandom() ：等概率随机返回一个现有值。 getMedian() ：返回当前所有值的中位数。若元素数量为偶数，返回中间两个值的平均值。要求所有操作的平均时间复杂度为 O(1) （ getMedian 除外，其要求平均 O(1) 但需巧妙设计）。解题过程循序渐进讲解第一步：分析核心挑战哈希表通常支持 O(1) 的插入、删除、随机访问（通过数组索引），但随机返回元素值需要维护元素列表。中位数操作需要有序数据，传统做法需排序（O(n log n)）或使用堆（O(log n)），但题目要求平均 O(1)。关键矛盾：哈希表无序，而中位数需要顺序信息。因此需结合哈希表和有序结构，并维护动态顺序统计。第二步：借鉴“常数时间随机返回”的设计常用技巧：用哈希表（值 → 索引集合）和动态数组（存储值）结合，实现 O(1) 插入、删除、getRandom。数组支持随机索引访问。删除时，将数组末尾元素移到被删位置，更新哈希表，避免整体移动。例子：插入 [ 5, 5, 6]，数组为 [ 5, 5, 6 ]，哈希表为 {5→{0,1}, 6→{2}}。第三步：加入中位数操作的设计思路要在 O(1) 时间得到中位数，必须维护一个始终有序的序列，并快速定位中间位置。可行方案：双哈希表 + 双端队列扩展？不，仍需排序。更优方案：使用两个平衡的多重集合（MultiSet），模拟“双堆”但支持快速删除任意值。用两个平衡的 BST（如 TreeSet，但需支持重复值）或 “排序列表 + 哈希索引” 实现。但 BST 操作是 O(log n)，不符合 O(1) 要求。第四步：重新审视“平均 O(1)”的含义若允许近似中位数，可用“分桶统计”，但题目要求精确中位数。精确中位数在动态数据中必须维护有序性，插入删除最坏至少 O(log n)。但“平均 O(1)”可通过 “懒更新 + 周期重排” 实现：维护一个数组 sorted 作为缓存有序序列，一个哈希表 valToIndices 指向数组中的位置（多个重复值需记录多个索引）。插入时，将新值放到未排序的缓冲区 buffer 中（O(1)），并更新哈希表。删除时，标记该值在哈希表中的索引为“已删除”，不立即重排。当缓冲区大小达到阈值（如 √n），触发重排：合并 sorted 和 buffer ，重新排序，重建索引（O(n) 但分摊到 √n 次操作，平均 O(√n)）。中位数直接从有序数组 sorted 中间位置取（O(1)）。但此法不满足严格 O(1) 平均，是 O(√n)。第五步：严格 O(1) 中位数的理论可能性已知文献有 “动态顺序统计树” （如 Order Statistic Tree）可实现插入、删除、查询第 k 大均为 O(log n)。若要 O(1) 中位数，必须在插入删除时动态维护中间指针。一种方法：用 “双端可扩展数组 + 中位数指针” ：将数据分为三部分： left （小于中位数）、 mid （等于当前中位数的一组值）、 right （大于中位数）。用哈希表记录每个值所属部分（ left / mid / right ）及在部分内的位置。中位数即 mid 部分的第一个值（奇数总数）或 (mid首 + right首)/2 （偶数总数调整）。插入时，根据值与当前中位数比较，放入对应部分，并调整 mid 的边界，使 left 和 right 大小平衡。删除时类似调整。此方法在插入删除时只需 O(1) 的指针移动，但需细致维护重复值的存储结构。第六步：具体数据结构设计用 HashMap<Integer, LinkedHashSet<Integer>> valToIndices 记录每个值在数组中的索引集合（以便 O(1) 删除任意一个）。用 ArrayList<Integer> arr 存储实际值，支持 getRandom。用 TreeMap<Integer, Integer> countMap 记录每个值的频率（键有序）。用 int totalCount 记录总元素个数。中位数计算：从 TreeMap 中顺序遍历，找到第 (totalCount+1)/2 个值（中位数位置），因 TreeMap 按键有序，但值未按插入顺序，所以需用频次累加找到中位数所在的键。但 TreeMap 找中位数需 O(k) 时间（k 为不同键的数量），不满足 O(1)。第七步：最终可实现平均 O(1) 的折中方案插入、删除、getRandom 严格 O(1)。 getMedian 用“有序哈希”思想：维护一个 LinkedHashMap<Integer, Integer> 记录值频次，并保持键按值大小排序（插入时用二分查找确定位置，但会破坏 O(1)）。实际上，若要严格 O(1) 中位数，必须牺牲部分操作的简洁性，或使用复杂的数据结构（如“哈希表 + 中位数指针 + 左右平衡链”）。工程中可接受近似 O(1)，用“分桶计数+中位数缓存”，每次插入删除更新中位数缓存。示例操作流程数据结构： List<Integer> arr = [5, 3, 5, 7] Map<Integer, LinkedHashSet<Integer>> valToIdx = {5->{0,2}, 3->{1}, 7->{3}} TreeMap<Integer, Integer> countMap = {3:1, 5:2, 7:1} 有序计数。 getMedian() ： totalCount=4，中位数位置 2.5（第2和第3个数的平均）。从 countMap 累加频次：3(1) -> 位置1；5(2) -> 位置2-3；所以中位数是 (5+5)/2=5。删除一个 5：从 valToIdx[ 5] 取一个索引 0，将 arr[ 0] 与 arr 末尾交换（arr[ 3]=7 换到 0），更新 valToIdx[ 7] 的索引从 {3} 改为 {0}，删除 arr 末尾，valToIdx[ 5 ] 移除 0。 countMap[ 5 ] 减为 1。总结本题结合了哈希表、动态数组、有序计数映射，核心在于：用哈希+数组实现 O(1) 插入、删除、随机返回。用有序计数映射（TreeMap）计算中位数，时间复杂度 O(k)（k 为不同值个数），若值域有限可优化为 O(1)。若要完全满足 O(1) 中位数，需使用更复杂的“双哈希表 + 中位数指针平衡”结构，但实现较为复杂。