问题描述

创建一个数据结构，可以存储一个可以随时间动态变化大小的整数列表，并在常数时间内 O(1) 找到这个动态增长列表的中位数。

实现一个名为 MedianOfStream 的结构体

该结构体应该提供以下功能：

• Init()：初始化数据结构，设置必要的组件来管理整数流，例如创建最大堆和最小堆。

• Insert Num(num)：向数据结构中添加一个整数 num。

• Find Median()：找到当前所有元素的中位数。如果元素数量为偶数，返回中间两个值的平均值。

约束条件

• 整数 num 满足以下约束：-10^5 ≤ num ≤ 10^5。
• 在计算中位数之前，数据结构中至少有一个元素。
• 最多会调用 500 次计算中位数的函数。

求中位数步骤

• 首先：是对数字排序
• 然后：如果数组是奇数的话，中位数就是中间的值 (start+end)/2
• 最后：如果是偶数的话，中位数是中间两个数加起来除以 (mid+mid+1)/2

那我们直接对数组排序，然后就这样就不就可以了吗？

得以O(1)常数时间内查找到才可以，但是步骤还是那个步骤，只是sort放在了heap里面利用maxheap和miniheap插入元素上浮和下移的性质就可以做到排序。

那应该怎么样插入数据呢？

我们让最小堆放素组中较大的一半元素，最大堆放较小的。

使用堆的思路

1. 两个堆的概念：
   • 最大堆 (maxHeap)：存储较小的一半数据，堆顶是这一部分的最大值。
   • 最小堆 (minHeap)：存储较大的一半数据，堆顶是这一部分的最小值。
2. 堆的平衡：
   • 通过保持两个堆的大小差不超过1，可以保证中位数始终处于堆顶或堆顶的平均值中。
   • 如果数据流中的元素个数为奇数，中位数为元素较多的那个堆的堆顶元素。
   • 如果数据流中的元素个数为偶数，中位数为两个堆的堆顶元素的平均值。

插入数据的具体步骤

1. 判断插入位置：
   • 如果新元素小于或等于最大堆的堆顶元素，将其插入最大堆。
   • 否则，将其插入最小堆。
2. 调整堆的大小：
   • 插入元素后，检查两个堆的大小。如果某个堆的元素数量超过另一个堆超过1个，则需要将该堆的堆顶元素移动到另一个堆中，以保持平衡。
   • 例如，如果 maxHeap 的元素比 minHeap 多2个，则将 maxHeap 的堆顶元素移动到 minHeap。
3. 查找中位数：
   • 当两个堆的大小相等时，中位数是两个堆顶元素的平均值。
   • 当两个堆的大小不相等时，中位数是元素较多的那个堆的堆顶元素。

代码如下：

插入数据示例

假设插入的顺序是 [5, 15, 1, 3]，插入过程如下：

• 插入 5：
  • maxHeap：[5]
  • minHeap：[]
  • 中位数：5
• 插入 15：
  • maxHeap：[5]
  • minHeap：[15]
  • 中位数：(5 + 15) / 2 = 10
• 插入 1：
  • maxHeap：[5, 1]
  • minHeap：[15]
  • 中位数：5
• 插入 3：
  • 平衡堆：[3, 1]，[5, 15]
  • 中位数：(3 + 5) / 2 = 4

总结

通过最大堆和最小堆的配合，可以有效地管理数据流，并在 O(1) 时间内查找中位数。插入操作的复杂度为 O(log n)，但查找中位数的操作只需要查看堆顶元素，时间复杂度为 O(1)。