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

题目描述
你需要设计一个数据结构，能够高效地处理一个数据流，并实时返回一个固定大小的滑动窗口内的中位数。这个数据结构应支持以下两种操作：

1. addNum(int num) ：将数据流中的一个新整数 num 添加到滑动窗口的右侧（即最新位置）。
2. findMedian() ：返回当前滑动窗口内所有整数的中位数。如果窗口大小是偶数，中位数是中间两个数的平均值。

核心约束：滑动窗口的大小是固定的，设为 k。当窗口已满（即已添加的数据量等于 k）后，再添加一个新元素时，窗口左侧最旧的元素会被移出，新元素从右侧加入。要求 addNum 和 findMedian 操作的平均时间复杂度尽可能低。

应用场景：例如，在实时监控系统中，需要持续计算最近一段时间（如最近5分钟）内某项指标（如请求延迟、CPU使用率）的中位数，以评估系统的整体表现。

解题过程循序渐进讲解

第一步：理解问题与挑战

首先，我们需要明确中位数的定义和计算方式。对于一个有序数组，如果其长度为奇数，中位数是中间那个数；如果长度为偶数，则是中间两个数的平均值。

最直接的想法是，在内部维护一个当前滑动窗口的数组。每次 addNum 时：

1. 将新元素加入数组。
2. 如果数组长度超过 k，则移除最老的元素（即数组第一个元素）。
3. 为了求中位数，需要对当前窗口数组进行排序，然后找到中间位置的数。

这种方法，addNum 操作涉及到插入、删除和排序，时间复杂度为 O(k log k) 或 O(k)（如果使用插入排序维护有序数组）。findMedian 是 O(1)。当 k 很大时，addNum 的效率很低。我们的目标是优化这个过程。

核心洞察：我们不需要在每次查询时都对整个窗口排序。我们可以在添加/删除元素的同时，动态地维护窗口元素的有序结构，以便快速获取中位数。这通常需要使用能够高效维护有序集合的数据结构，并结合哈希表来快速定位和删除指定元素。

第二步：选择核心数据结构 - 对顶堆 + 延迟删除

在静态数据流中求中位数，经典且高效的方法是使用两个堆：

• 最大堆（small）：存储较小的一半数字，堆顶是这半部分的最大值。
• 最小堆（large）：存储较大的一半数字，堆顶是这半部分的最小值。

维护两个堆，使得它们的大小满足：

1. small 的大小要么等于 large 的大小（当总数为偶数时），要么比 large 大1（当总数为奇数时）。
2. small 的所有元素 <= large 的所有元素。

这样，中位数就可以直接从两个堆的堆顶获得。

然而，在滑动窗口场景中，存在“删除最旧元素”的操作。堆本身不支持删除任意指定值的元素（除非遍历，效率低）。为了解决这个问题，我们需要引入延迟删除技术。

延迟删除的精髓：

• 我们并不在元素离开窗口时立即从堆中删除它。
• 我们用一个哈希表（delayed）记录每个待删除元素及其应被删除的次数。
• 在每次进行涉及堆顶的操作（如插入、取堆顶）前，我们“清理”堆顶：检查堆顶元素是否在 delayed 哈希表中，如果是，则弹出它（执行删除），并更新哈希表中的计数，直到堆顶元素是有效的。
• 同时，我们需要一个计数器来记录两个堆的“有效”元素数量（即实际在窗口内的元素），以判断何时需要调整两个堆的平衡。

第三步：详细设计数据结构

我们定义以下数据结构成员：

class MedianFinder {
private:
    // 核心数据结构
    priority_queue<int> small; // 最大堆，存储较小一半
    priority_queue<int, vector<int>, greater<int>> large; // 最小堆，存储较大一半
    // 辅助数据结构
    unordered_map<int, int> delayed; // 延迟删除哈希表， key: 待删除数字, value: 待删除次数
    int smallSize = 0; // small堆中有效元素的数量
    int largeSize = 0; // large堆中有效元素的数量
    int k; // 滑动窗口大小
    queue<int> window; // 用一个队列来记录窗口内元素的顺序，便于知道哪个元素该被移除

第四步：定义关键辅助操作 - prune 和 makeBalance

1. prune(heap) 操作：
   这个函数用于清理一个堆（small 或 large）的堆顶。它会不断地弹出堆顶，如果堆顶元素在 delayed 哈希表中，就执行真正的删除（减少计数，如果计数为0则移除key）。直到堆顶是有效元素或堆为空。

   template<typename T>
   void prune(T& heap) {
       while (!heap.empty()) {
           int num = heap.top();
           if (delayed.count(num)) {
               heap.pop();
               if (--delayed[num] == 0) {
                   delayed.erase(num);
               }
           } else {
               break; // 遇到有效元素，停止清理
           }
       }
   }
   

2. makeBalance() 操作：
   在插入或删除元素后，需要确保两个堆的大小关系满足我们的约定（smallSize >= largeSize 且 smallSize - largeSize <= 1）。如果不满足，就从元素多的堆弹出堆顶，插入到元素少的堆，并更新对应的有效大小。在移动元素后，需要对来源堆进行 prune 操作，因为它刚刚被弹出了堆顶。

   void makeBalance() {
       // 如果small堆中有效元素比large堆多2个或更多
       if (smallSize > largeSize + 1) {
           // 从small移动一个到large
           large.push(small.top());
           small.pop();
           smallSize--;
           largeSize++;
           // 因为small刚弹出堆顶，需要清理其可能的无效堆顶
           prune(small);
       } else if (largeSize > smallSize) {
           // 如果large堆有效元素比small堆多
           small.push(large.top());
           large.pop();
           smallSize++;
           largeSize--;
           // 清理large堆顶
           prune(large);
       }
   }
   

第五步：实现 addNum 和 findMedian

1. addNum(int num) 步骤：
   a. 处理窗口满的情况：如果当前窗口已满（window.size() == k），我们需要移除最旧的元素。
   * 从队列 window 中获取要移除的元素 outNum。
   * 将 outNum 加入到 delayed 哈希表（计数+1）。
   * 判断 outNum 原本应该在哪个堆。如果 outNum <= small.top()，那么它应该在 small 中，因此 smallSize--。否则，它应该在 large 中，largeSize--。
   * 对两个堆都执行 prune 操作，因为移除操作可能导致某个堆的堆顶变为待删除元素。
   b. 插入新元素：
   * 将新元素 num 加入 window 队列。
   * 如果 small 为空 或 num <= small.top()，将 num 加入 small 堆，smallSize++。
   * 否则，将 num 加入 large 堆，largeSize++。
   c. 重新平衡：调用 makeBalance() 使两个堆的有效大小关系恢复约定。

2. findMedian() 步骤：
   a. 首先，对两个堆的堆顶都执行 prune 操作，确保我们看到的堆顶是有效的。
   b. 如果 k 是奇数，中位数就是 small 的堆顶（因为我们约定 smallSize >= largeSize 且最多大1）。
   c. 如果 k 是偶数，中位数是 (small.top() + large.top()) / 2.0。

第六步：复杂度分析

• 时间复杂度：
  • addNum: 每次操作涉及堆的插入（O(log k)）、prune 和 makeBalance（最坏情况也是 O(log k)）。由于每个元素只会被加入延迟删除哈希表一次，并在某次 prune 中被弹出一次，所以摊还时间复杂度是 O(log k)。
  • findMedian: 主要是两次 prune 操作，摊还时间复杂度同样是 O(log k)。
• 空间复杂度：O(k)，用于存储窗口元素、两个堆和延迟删除哈希表。

第七步：示例演示

假设 k=3，操作序列为: addNum(1), addNum(2), findMedian(), addNum(3), findMedian(), addNum(4), findMedian()。

1. addNum(1): window=[1], small=[1], smallSize=1, large=[], largeSize=0.
2. addNum(2): window=[1,2], 2 > small.top(1), 入large。small=[1], smallSize=1, large=[2], largeSize=1. 平衡检查通过。
3. findMedian(): k=3是奇数，返回small.top()=1？等等，此时smallSize=1, largeSize=1，总数2？出错！我们还没添加第3个数，窗口未满，findMedian 的语义是返回当前窗口内所有数的中位数，当前窗口只有[1,2]。所以这里应该返回(1+2)/2=1.5。这说明在窗口未满时，我们的“两个堆”约定（small比large最多多1）是基于总元素数的。在窗口未满时，约定应基于当前总有效元素数。算法需要做简单调整：在findMedian时，先判断当前总有效元素数（smallSize+largeSize）是奇是偶，再决定如何计算。我们继续按窗口满的情况（k=3）推演。
4. addNum(3): 窗口未满，继续添加。3 > small.top(1)，入large。window=[1,2,3]。small=[1], smallSize=1, large=[2,3], largeSize=2。此时 largeSize > smallSize，需要平衡。从large弹出堆顶2，加入small。small=[2,1], large=[3]。更新大小: smallSize=2, largeSize=1。清理large（堆顶3有效）。
5. findMedian(): 窗口满，k=3是奇数。prune后small.top=2, large.top=3。总有效数=3，是奇数，中位数应为第2小的数，即small的堆顶2。正确（窗口[1,2,3]的中位数是2）。
6. addNum(4): 窗口已满，需移除最旧的1，加入4。
   • 移除1: delayed[1]++。1 <= small.top(2)，所以它应在small中，smallSize-- (从2变为1)。prune(small): small堆顶是2，不是1，不清理。prune(large): 堆顶3，有效。
   • 加入4: 4 > small.top(2)? 是的，入large。window=[2,3,4]。small=[2], smallSize=1, large=[3,4], largeSize=2。
   • 平衡: largeSize(2) > smallSize(1)，从large移动3到small。small=[3,2], large=[4]。smallSize=2, largeSize=1。prune(large): 堆顶4有效。
7. findMedian(): 窗口[2,3,4]，中位数是3。small.top()是3，正确。

这个示例验证了算法的核心流程，包括延迟删除和重新平衡。注意，在实现时，findMedian 需要根据当前有效总数（smallSize+largeSize）来判断奇偶性，而不是直接用固定的k，以处理窗口未满的初始化阶段。当窗口满后，有效总数恒为k。