哈希算法题目：设计一个基于哈希的滑动窗口中位数查找结构 题目描述 设计一个数据结构，它能高效地计算一个滑动窗口内的中位数。该结构需要支持以下操作： SlidingWindowMedian(int windowSize) ：初始化数据结构， windowSize 是滑动窗口的大小。 addNum(int num) ：向数据结构中添加一个新数字。如果窗口已满（即已添加的数字数量等于 windowSize ），在添加新数字后，最早添加的数字（即窗口最左侧的数字）会被移除以保持窗口大小不变。 findMedian() ：返回当前滑动窗口中所有数字的中位数。如果窗口大小为偶数，中位数是中间两个数的平均值；如果为奇数，则是中间那个数。 要求 addNum 和 findMedian 操作的时间复杂度尽可能低。 解题思路 直接对窗口内的数字排序或每次查找时排序，时间复杂度会很高。一个高效的方法是使用两个堆（一个大顶堆存储较小的一半数字，一个小顶堆存储较大的一半数字）来动态维护中位数，这通常能实现 O(log n) 的插入和 O(1) 的查询。但这里有一个关键挑战： 窗口是滑动的，我们需要支持删除任意元素（当窗口满时，需要删除最早的那个数字） 。标准堆（优先队列）不支持在 O(log n) 时间内删除任意指定元素。 核心思路 ：采用“延迟删除”策略。我们维护两个堆（ small 大顶堆，存储较小的一半； large 小顶堆，存储较大的一半），并始终平衡，使 small 的大小 >= large 的大小（最多大1），这样中位数就可以从堆顶快速获取。同时，我们使用一个哈希表（ delayed ）来记录那些应该被删除但尚未从堆中弹出的元素及其数量。当这些元素出现在堆顶时，我们才将其弹出。这样，添加和删除操作都可以在 O(log k) 时间内完成（k 是窗口大小），查找中位数是 O(1)。 详细步骤 数据结构定义 ： small ：一个最大堆（Python 中用负数模拟），存储当前窗口内数值较小的一半元素。堆顶是这一半中的最大值。 large ：一个最小堆，存储当前窗口内数值较大的一半元素。堆顶是这一半中的最小值。 delayed ：一个哈希表（字典），键为应该被删除的元素值，值为该值待删除的次数（因为窗口中可能有重复数字）。 我们还需要记录 small 和 large 中实际有效的元素数量（即减去待删除元素后的数量），我们用变量 smallSize 和 largeSize 来记录，而不是直接取堆的长度。 windowSize ：窗口大小。 一个队列（如双端队列） window 用于按顺序存储窗口内的所有元素，以便在窗口满时知道要删除哪个最早的元素。 辅助方法 ： prune(heap) ：如果 heap 的堆顶元素存在于 delayed 中，且待删除次数大于0，则弹出堆顶，并减少 delayed 中对应计数，直到堆顶是一个有效元素。 makeBalance() ：调整 small 和 large 的大小，使得 smallSize 要么等于 largeSize ，要么比 largeSize 大1，以满足中位数的定义。如果失衡，就从元素多的堆中弹出堆顶，推入另一个堆，并更新对应的 size 变量。 操作流程 ： 添加数字 ( addNum ) 将新数字 num 加入队列 window 。 如果 small 为空或 num <= -small[0] （即小于等于 small 的最大值），则将 num 加入 small （大顶堆用负数存储），并将 smallSize 加1。否则，将 num 加入 large ， largeSize 加1。 调用 makeBalance() 重新平衡两个堆。 如果此时队列 window 的长度超过了 windowSize ，说明窗口满了，需要移除最早的元素： 从 window 中弹出最早的元素 outNum 。 在 delayed 哈希表中增加 outNum 的待删除计数： delayed[outNum] = delayed.get(outNum, 0) + 1 。 确定 outNum 原本属于哪个堆： 如果 outNum <= -small[0] （这里需要先调用 prune 确保堆顶有效），则它应该在 small 中，将 smallSize 减1。否则，将 largeSize 减1。 然后，调用 prune(small) 和 prune(large) 清理堆顶的无效元素。 再次调用 makeBalance() 确保平衡。 查找中位数 ( findMedian ) 调用 prune(small) 和 prune(large) 确保堆顶有效。 如果 windowSize 是奇数，中位数就是 small 的堆顶（取负数）。如果 windowSize 是偶数，中位数是 (-small[0] + large[0]) / 2.0 。 示例 假设 windowSize = 3 ，操作序列为： addNum(1) , addNum(3) , findMedian() , addNum(5) , findMedian() , addNum(2) , findMedian() 。 初始化： small = [] , large = [] , delayed = {} , window = [] , smallSize = 0 , largeSize = 0 。 addNum(1) : window = [1] small 为空，将1加入 small -> small = [-1] , smallSize = 1 平衡： smallSize=1 , largeSize=0 ，满足条件。 addNum(3) : window = [1, 3] 3 > -(-1) -> 加入 large -> large = [3] , largeSize=1 平衡： smallSize=1 , largeSize=1 ，满足条件。 findMedian() : 窗口大小3为奇数，中位数是 small 的堆顶： -(-1) = 1 ? 等等，这里需要检查当前有效窗口大小是2（因为还没满），但题目是滑动窗口， findMedian 应该在窗口满时才返回有效中位数？实际上，在这个数据结构定义中， findMedian 应该只在窗口已满（即已添加数字数量等于 windowSize ）时才返回正确中位数，但实现上可以处理不满的情况，不过题目通常要求窗口满。我们假设只在窗口满时才调用 findMedian 。为了流程完整，我们继续。 当前窗口内数字是 [ 1, 3]，中位数是 (1+3)/2=2。我们的结构： small=[-1] , large=[3] ，中位数是 (-(-1) + 3)/2 = 2 ，正确。 addNum(5) : window = [1, 3, 5] ，窗口满。 5 > -(-1) -> 加入 large -> large = [3,5] 堆化后为 [ 3,5]? 实际堆内顺序可能为 [ 3,5]，但堆顶是3。 largeSize=2 平衡： smallSize=1 , largeSize=2 ，不满足（ smallSize 应 >= largeSize ）。从 large 弹出堆顶3，加入 small （加入-3）。 large 弹出3后变为 [ 5], largeSize=1 small 加入-3后变为 [ -3, -1]（堆顶是-3）， smallSize=2 现在 smallSize=2 , largeSize=1 ，满足 smallSize = largeSize + 1 。 findMedian() : 窗口大小3为奇数，中位数是 small 的堆顶： -(-3) = 3 。窗口 [ 1,3,5 ] 的中位数是3，正确。 addNum(2) : 窗口已满，需要先移除最早的元素1，再加入2。 加入2: window 先加入2 -> window = [3,5,2] 2 <= -(-3) -> 加入 small -> small = [-3,-1,-2] ? 插入-2后堆化为 [ -3,-2,-1]，堆顶是-3。 smallSize=3 （注意，我们还没调整删除） 需要删除最早的元素1： 1 在 delayed 中增加计数: delayed[1] = 1 。 判断1属于哪个堆：1 <= -(-3) 成立，所以它应该在 small 中， smallSize 减1 -> smallSize=2 。 调用 prune(small) : 堆顶是-3，对应数字3，不在 delayed 中，不弹出。 调用 prune(large) : 堆顶是5，不在 delayed 中。 调用 makeBalance() : 现在 smallSize=2 , largeSize=1 ，满足条件，无需调整。 最终窗口为 [ 3,5,2]，排序后为 [ 2,3,5]，中位数应为3。检查我们的结构： small=[-3,-2,-1] 堆顶-3， large=[5] ， smallSize=2 , largeSize=1 ，中位数是 small 堆顶3，正确。 关键点总结 延迟删除：通过哈希表记录待删除元素，避免在堆中直接搜索删除，将删除操作平摊到后续的 prune 中。 平衡维护：通过 smallSize 和 largeSize 跟踪有效元素数量，确保中位数可以从堆顶快速获得。 时间复杂度： addNum 和 findMedian 的平摊时间复杂度为 O(log k)，其中 k 是窗口大小。空间复杂度 O(k)。 这个结构巧妙地将哈希表（用于延迟删除）与堆（用于维护有序性）结合起来，高效解决了滑动窗口中位数查找的难题。