随机选择一个尚未讲过的哈希算法相关题目：

字数 3745 2025-12-15 09:34:49

随机选择一个尚未讲过的哈希算法相关题目：

哈希算法题目：设计一个基于哈希的滑动窗口中位数查找结构

题目描述：

假设有一个整数数据流不断进入。你能否设计一个数据结构，在任意时刻，都能高效地返回当前滑动窗口内的中位数？

我们需要具体化这个要求。通常，对于一个固定长度为 k 的滑动窗口，当窗口在数据流上滑动时，你可能会被要求实现以下操作：

MedianFinder 初始化，设定窗口大小 k。
add(val)：从数据流中读入一个新元素 val。这个操作会被连续调用。在第一次调用 k-1 次 add 后，滑动窗口被填满。之后每次 add，都会在窗口尾部加入新值，并从窗口头部移除一个旧值（滑动）。
findMedian()：返回当前滑动窗口内所有元素的中位数。如果窗口大小 k 是奇数，中位数是排序后中间的那个数；如果是偶数，则是中间两个数的平均值。

这个问题的挑战在于：

窗口是动态滑动的，元素不断加入和移除。
需要快速找到中位数，这通常需要对窗口内元素进行排序或快速定位中间值。
直接对窗口内元素排序，每次操作的复杂度是 O(k log k)，当数据流很大时效率很低。

我们需要利用哈希表结合其他数据结构，设计一个更高效的方案。

解题过程循序渐进讲解：

步骤1：明确目标与核心思路

我们的核心目标是：在 O(log k) 或 O(1) 的时间复杂度内完成元素的添加/移除和中位数的查找。

一个经典高效的方法是使用双优先队列（堆） 来维护数据流的中位数，例如一个大顶堆存储较小的一半数，一个小顶堆存储较大的一半数，保持两堆大小平衡，中位数就从堆顶获取。这个方法对于静态集合或只增加元素的流很有效，但它不支持高效地删除任意元素（我们的滑动窗口需要移除最旧的元素）。

为了支持删除，一个常用的技巧是“延迟删除”。我们维护两个堆（small 大顶堆，large 小顶堆），并用一个哈希表（delayed） 来记录需要删除但尚未从堆中弹出的元素及其待删除次数。同时，我们还需要知道窗口内哪些元素是“有效的”（即未被移出窗口的）。

步骤2：数据结构设计

我们定义以下成员变量：

maxHeap (small): 一个最大堆（Python 中通过取负数实现），存储窗口中较小的一半数字。
minHeap (large): 一个最小堆，存储窗口中较大的一半数字。
delayed: 一个哈希表（字典），key 为需要删除的数字，value 为该数字待删除的次数（因为窗口内可能有重复数字）。
k: 滑动窗口的大小。
smallSize, largeSize: 分别记录 maxHeap 和 minHeap 中有效元素的数量（不包括已标记删除的）。
注意：我们还需要一个队列（如 deque）来按顺序记录窗口中的所有元素，以便在窗口滑动时知道要移除哪个元素。

步骤3：操作定义与平衡规则

我们定义两个关键的内部操作：

prune(pq): 清理堆 pq 的堆顶元素，如果堆顶元素在 delayed 中被标记为待删除，则弹出它并更新 delayed 计数。重复此过程，直到堆顶元素是有效的。
makeBalance(): 调整两个堆的大小，使得它们满足平衡条件。我们的平衡规则是：
- 如果 k 是奇数，让 smallSize 比 largeSize 多1。
- 如果 k 是偶数，让 smallSize 等于 largeSize。
  如果不满足，就从元素多的堆弹出堆顶元素，插入到另一个堆，并调用 prune 确保移动的是有效元素。

步骤4：add(val) 操作详解

入队：将新值 val 添加到我们维护的窗口队列尾部。
插入堆：
- 如果 maxHeap 为空或 val <= maxHeap 的堆顶（即当前较小一半的最大值），则将 val 加入 maxHeap，并增加 smallSize。
- 否则，将 val 加入 minHeap，并增加 largeSize。
平衡调整：调用 makeBalance() 函数，确保两个堆的大小关系满足我们的平衡规则。
滑动窗口：如果当前窗口队列长度超过 k，说明需要移除最旧的元素。
- 从队列头部弹出待移除的元素 remove_val。
- 在哈希表 delayed 中，将 remove_val 的待删除计数加1。注意，这里只是标记，不是立即从堆中删除。
- 判断 remove_val 原本属于哪个堆：
  - 如果 remove_val <= maxHeap 的堆顶（注意，此时堆顶可能已被标记删除，但我们比较的是值），则认为它理论上属于 maxHeap，将 smallSize 减1。
  - 否则，认为它属于 minHeap，将 largeSize 减1。
- 调用 prune(maxHeap) 和 prune(minHeap)，清理两个堆顶可能存在的已标记删除的元素。
再次平衡：由于移除了一个元素，堆的大小可能再次失衡，因此需要再次调用 makeBalance()。

步骤5：findMedian() 操作详解

在执行 findMedian() 之前，我们可以先调用 prune 清理一下两个堆的堆顶，确保堆顶有效。

如果 k 是奇数，中位数就是 maxHeap 的堆顶元素（因为 smallSize 更大）。
如果 k 是偶数，中位数是 (maxHeap 堆顶 + minHeap 堆顶) / 2.0。

步骤6：复杂度分析

时间复杂度：add 操作中，每次插入堆是 O(log k)，prune 操作平均是 O(1)（因为每个元素最多被清理一次），makeBalance 也是 O(log k)。所以每次 add 操作平均时间复杂度为 O(log k)。findMedian 是 O(1)。
空间复杂度：O(k)，用于存储窗口元素、两个堆和哈希表。

步骤7：举例说明

假设 k=3，数据流为 [1, 3, 2, 5, ...]。
初始化：maxHeap=[], minHeap=[], delayed={}, smallSize=0, largeSize=0, 队列 queue=[]。

add(1):
- queue=[1]。1 加入 maxHeap -> maxHeap=[-1], smallSize=1.
- 无需平衡 (窗口未满)。
add(3):
- queue=[1,3]。3 > 当前maxHeap顶(-1的负值=1)，加入 minHeap -> minHeap=[3], largeSize=1.
- 无需平衡 (窗口未满)。
add(2):
- queue=[1,3,2]。2 <= maxHeap顶(1)？不成立(2>1)，加入 minHeap -> minHeap=[2,3], largeSize=2.
- 需要平衡：smallSize=1, largeSize=2。从minHeap弹出堆顶2，加入maxHeap -> maxHeap=[-2,-1], minHeap=[3]。更新smallSize=2, largeSize=1。
- 窗口已满。调用 findMedian(): k是奇数，中位数=maxHeap顶=-2的负值=2。
add(5) (窗口滑动):
- queue=[1,3,2,5] (加入5)。5 > maxHeap顶(2)? 是，加入minHeap -> minHeap=[3,5], largeSize=2.
- 平衡：smallSize=2, largeSize=2 (偶数k，期望相等)，平衡。
- 移除队首元素1: queue变为[3,2,5]。在delayed中记录 delayed[1]=1。1属于maxHeap吗？1 <= maxHeap顶(2)？是，所以smallSize减1 -> smallSize=1。
- 清理堆顶: prune(maxHeap)，堆顶是-2(值2)，不在delayed中，停止。prune(minHeap)，堆顶是3，不在delayed中。
- 再次平衡: smallSize=1, largeSize=2。从minHeap弹出3加入maxHeap -> maxHeap=[-3,-2], minHeap=[5]。smallSize=2, largeSize=1。
- 调用 findMedian(): 中位数=maxHeap顶=-3的负值=3。

这个数据结构巧妙地结合了堆（用于快速获取最值/中位数）和哈希表（用于延迟删除），从而高效地解决了滑动窗口中位数查找的难题。

随机选择一个尚未讲过的哈希算法相关题目：哈希算法题目：设计一个基于哈希的滑动窗口中位数查找结构题目描述：假设有一个整数数据流不断进入。你能否设计一个数据结构，在任意时刻，都能高效地返回当前滑动窗口内的中位数？我们需要具体化这个要求。通常，对于一个固定长度为 k 的滑动窗口，当窗口在数据流上滑动时，你可能会被要求实现以下操作： MedianFinder 初始化，设定窗口大小 k 。 add(val) ：从数据流中读入一个新元素 val 。这个操作会被连续调用。在第一次调用 k-1 次 add 后，滑动窗口被填满。之后每次 add ，都会在窗口尾部加入新值，并从窗口头部移除一个旧值（滑动）。 findMedian() ：返回当前滑动窗口内所有元素的中位数。如果窗口大小 k 是奇数，中位数是排序后中间的那个数；如果是偶数，则是中间两个数的平均值。这个问题的挑战在于：窗口是动态滑动的，元素不断加入和移除。需要快速找到中位数，这通常需要对窗口内元素进行排序或快速定位中间值。直接对窗口内元素排序，每次操作的复杂度是 O(k log k)，当数据流很大时效率很低。我们需要利用哈希表结合其他数据结构，设计一个更高效的方案。解题过程循序渐进讲解：步骤1：明确目标与核心思路我们的核心目标是：在 O(log k) 或 O(1) 的时间复杂度内完成元素的添加/移除和中位数的查找。一个经典高效的方法是使用双优先队列（堆）来维护数据流的中位数，例如一个大顶堆存储较小的一半数，一个小顶堆存储较大的一半数，保持两堆大小平衡，中位数就从堆顶获取。这个方法对于静态集合或只增加元素的流很有效，但它不支持高效地删除任意元素（我们的滑动窗口需要移除最旧的元素）。为了支持删除，一个常用的技巧是“ 延迟删除 ”。我们维护两个堆（ small 大顶堆， large 小顶堆），并用一个哈希表（ delayed ）来记录需要删除但尚未从堆中弹出的元素及其待删除次数。同时，我们还需要知道窗口内哪些元素是“有效的”（即未被移出窗口的）。步骤2：数据结构设计我们定义以下成员变量： maxHeap (small): 一个最大堆（Python 中通过取负数实现），存储窗口中较小的一半数字。 minHeap (large): 一个最小堆，存储窗口中较大的一半数字。 delayed : 一个哈希表（字典）， key 为需要删除的数字， value 为该数字待删除的次数（因为窗口内可能有重复数字）。 k : 滑动窗口的大小。 smallSize , largeSize : 分别记录 maxHeap 和 minHeap 中有效元素的数量（不包括已标记删除的）。注意：我们还需要一个队列（如 deque ）来按顺序记录窗口中的所有元素，以便在窗口滑动时知道要移除哪个元素。步骤3：操作定义与平衡规则我们定义两个关键的内部操作： prune(pq) : 清理堆 pq 的堆顶元素，如果堆顶元素在 delayed 中被标记为待删除，则弹出它并更新 delayed 计数。重复此过程，直到堆顶元素是有效的。 makeBalance() : 调整两个堆的大小，使得它们满足平衡条件。我们的平衡规则是：如果 k 是奇数，让 smallSize 比 largeSize 多1。如果 k 是偶数，让 smallSize 等于 largeSize 。如果不满足，就从元素多的堆弹出堆顶元素，插入到另一个堆，并调用 prune 确保移动的是有效元素。步骤4： add(val) 操作详解入队：将新值 val 添加到我们维护的窗口队列尾部。插入堆：如果 maxHeap 为空或 val <= maxHeap 的堆顶（即当前较小一半的最大值），则将 val 加入 maxHeap ，并增加 smallSize 。否则，将 val 加入 minHeap ，并增加 largeSize 。平衡调整：调用 makeBalance() 函数，确保两个堆的大小关系满足我们的平衡规则。滑动窗口：如果当前窗口队列长度超过 k ，说明需要移除最旧的元素。从队列头部弹出待移除的元素 remove_val 。在哈希表 delayed 中，将 remove_val 的待删除计数加1。注意，这里只是标记，不是立即从堆中删除。判断 remove_val 原本属于哪个堆：如果 remove_val <= maxHeap 的堆顶（注意，此时堆顶可能已被标记删除，但我们比较的是值），则认为它理论上属于 maxHeap ，将 smallSize 减1。否则，认为它属于 minHeap ，将 largeSize 减1。调用 prune(maxHeap) 和 prune(minHeap) ，清理两个堆顶可能存在的已标记删除的元素。再次平衡：由于移除了一个元素，堆的大小可能再次失衡，因此需要再次调用 makeBalance() 。步骤5： findMedian() 操作详解在执行 findMedian() 之前，我们可以先调用 prune 清理一下两个堆的堆顶，确保堆顶有效。如果 k 是奇数，中位数就是 maxHeap 的堆顶元素（因为 smallSize 更大）。如果 k 是偶数，中位数是 ( maxHeap 堆顶 + minHeap 堆顶) / 2.0。步骤6：复杂度分析时间复杂度： add 操作中，每次插入堆是 O(log k)， prune 操作平均是 O(1)（因为每个元素最多被清理一次）， makeBalance 也是 O(log k)。所以每次 add 操作平均时间复杂度为 O(log k)。 findMedian 是 O(1)。空间复杂度：O(k)，用于存储窗口元素、两个堆和哈希表。步骤7：举例说明假设 k=3 ，数据流为 [ 1, 3, 2, 5, ... ]。初始化： maxHeap =[], minHeap =[], delayed ={}, smallSize=0 , largeSize=0 , 队列 queue=[ ]。 add(1): queue=[ 1]。1 加入 maxHeap -> maxHeap =[ -1], smallSize=1 . 无需平衡 (窗口未满)。 add(3): queue=[ 1,3]。3 > 当前 maxHeap 顶(-1的负值=1)，加入 minHeap -> minHeap =[ 3], largeSize=1 . 无需平衡 (窗口未满)。 add(2): queue=[ 1,3,2]。2 <= maxHeap 顶(1)？不成立(2>1)，加入 minHeap -> minHeap =[ 2,3], largeSize=2 . 需要平衡： smallSize=1 , largeSize=2 。从 minHeap 弹出堆顶2，加入 maxHeap -> maxHeap =[ -2,-1], minHeap =[ 3]。更新 smallSize=2 , largeSize=1 。窗口已满。调用 findMedian(): k 是奇数，中位数= maxHeap 顶=-2的负值=2。 add(5) (窗口滑动): queue=[ 1,3,2,5] (加入5)。5 > maxHeap 顶(2)? 是，加入 minHeap -> minHeap =[ 3,5], largeSize=2 . 平衡： smallSize=2 , largeSize=2 (偶数k，期望相等)，平衡。移除队首元素1: queue变为[ 3,2,5]。在 delayed 中记录 delayed[1]=1 。1属于 maxHeap 吗？1 <= maxHeap 顶(2)？是，所以 smallSize 减1 -> smallSize=1 。清理堆顶: prune(maxHeap) ，堆顶是-2(值2)，不在 delayed 中，停止。 prune(minHeap) ，堆顶是3，不在 delayed 中。再次平衡: smallSize=1 , largeSize=2 。从 minHeap 弹出3加入 maxHeap -> maxHeap =[ -3,-2], minHeap =[ 5]。 smallSize=2 , largeSize=1 。调用 findMedian(): 中位数= maxHeap 顶=-3的负值=3。这个数据结构巧妙地结合了堆（用于快速获取最值/中位数）和哈希表（用于延迟删除），从而高效地解决了滑动窗口中位数查找的难题。