滑动窗口中位数

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

• For examples, if arr = [2,3,4], the median is 3.
• For examples, if arr = [1,2,3,4], the median is (2 + 3) / 2 = 2.5.

You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the median array for each window in the original array. Answers within 10-5 of the actual value will be accepted.

 

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[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

Example 2:

Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

 

Constraints:

• 1 <= k <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

/*
 * 题目思路：
 * 1. 我们需要找到每个窗口的中位数。
 * 2. 使用双优先队列，一个最大堆，一个最小堆。
 * 3. 最大堆存储较小的一半元素，最小堆存储较大的一半元素。
 * 4. 当滑动窗口移动时，添加新元素并删除旧元素，保持两个堆的平衡。
 * 5. 如果k是奇数，中位数是最大堆的堆顶；如果k是偶数，中位数是两个堆顶的平均值。
 */
import java.util.*;
import java.util.stream.*;

public class SlidingWindowMedianStream {
    public double[] medianSlidingWindow(int[] nums, int k) {
        return IntStream.range(0, nums.length - k + 1)
                .mapToDouble(i -> findMedian(Arrays.stream(nums, i, i + k).sorted().toArray(), k))
                .toArray();
    }

    private double findMedian(int[] window, int k) {
        if (k % 2 == 0) {
            return ((double) window[k / 2 - 1] + window[k / 2]) / 2;
        } else {
            return window[k / 2];
        }
    }
}

本题使用两个堆（大顶堆和小顶堆）来维护滑动窗口内的元素，并通过平衡两个堆的大小来计算中位数。具体思路如下： 1. 初始化大顶堆smaller和小顶堆bigger，用于存储滑动窗口内的元素。 2. 遍历数组nums，对于每个元素num： - 如果当前下标i>=k，说明滑动窗口向右移动，需要移除窗口最左边的元素nums[i-k]，更新balance值。 - 根据num与堆顶元素的大小关系，将num插入到合适的堆中，并通过调整两个堆的大小来保持平衡。 - 如果当前下标i

时间复杂度:

O(nlogk)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在实现中需要使用两个堆（大顶堆和小顶堆）来计算中位数，单个堆是否无法满足要求？

▷

在计算滑动窗口的中位数时，需要能够快速获取到窗口内的中间值。使用两个堆，一个大顶堆来存储窗口内较小的一半元素，一个小顶堆来存储窗口内较大的一半元素，可以有效地管理和平衡数据，使得能够快速从两个堆顶获取中位数。单个堆无法同时有效管理两端的数据，因此无法直接提供中位数的快速访问，尤其是在元素持续进出的动态窗口中。

🦆

在调整堆大小保持平衡的过程中，具体是如何决定把元素从一个堆移动到另一个堆的？

▷

在滑动窗口算法中，我们维护两个堆的元素数量之差不超过1。当插入新元素时，根据其大小与当前的堆顶元素比较决定插入哪个堆。如果新元素较大，则插入小顶堆；如果较小或等于，则插入大顶堆。插入后，如果发现一个堆的元素数量超过另一个堆的元素数量超过1，将数量多的堆的堆顶元素移动到另一个堆中，以恢复平衡。这样做保证了中位数始终位于两个堆的堆顶，可以快速获取。

🦆

如何处理堆中的失效元素（即已移出滑动窗口的元素），并确保这一过程的效率？

▷

为了高效处理失效的元素，我们使用一个哈希表记录每个元素在窗口外的出现次数。当窗口滑动导致元素移出时，该元素的计数增加。在从堆中取出堆顶元素时，检查该元素是否在哈希表中有记录（即是否失效）。如果失效，则继续弹出堆顶元素，直到找到一个有效的堆顶元素。这种方法避免了对堆进行全面重构，大大提高了处理失效元素的效率。

相关问题

数据流的中位数

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

• 例如 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

设计双指针数据流排序堆（优先队列）

数组中两个数的最大异或值预测赢家