数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。

• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

• -105 <= num <= 105
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 104 次调用 addNum 和 findMedian

/*
 * 思路：我们使用Stream API来简化插入排序的操作。
 * 1. 使用一个ArrayList来存储元素。
 * 2. 每次插入新元素时，将其插入到正确的位置以保持有序。
 * 3. 使用Stream来实现排序和中位数计算。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
 
class MedianFinder {
    private List<Integer> nums;
 
    public MedianFinder() {
        nums = new ArrayList<>();
    }
 
    public void addNum(int num) {
        nums.add(num);
        nums = nums.stream().sorted().collect(Collectors.toList());
    }
 
    public double findMedian() {
        int size = nums.size();
        if (size % 2 == 1) {
            return nums.get(size / 2);
        } else {
            return (nums.get(size / 2 - 1) + nums.get(size / 2)) / 2.0;
        }
    }
}
 

这个题解使用了两个堆来实现数据流的中位数查找。左边的堆是一个大顶堆，存储较小的一半数据；右边的堆是一个小顶堆，存储较大的一半数据。通过维护两个堆的大小平衡，并且保证左边堆的最大值小于等于右边堆的最小值，就可以在 O(1) 的时间复杂度内找到中位数。当数据总数为奇数时，中位数就是左边堆的堆顶元素；当数据总数为偶数时，中位数就是左右两个堆堆顶元素的平均值。

O(log n)

O(n)

窗口位置                      中位数
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7      -1
 1  3 [-1  -3  5] 3  6  7      -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6