LeetCode每日一题（2021-2-3 滑动窗口中位数）

题目描述

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

● [2,3,4]，中位数是 3
● [2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

示例：
在这里插入图片描述

解题思路

话说力扣上个月的每日一题都是并查集，这个月看来是要和滑动窗口杠上了，不过这种按标签练习题目的效果还是挺不错的，能比较牢固地掌握这个知识点。

首先最容易想到的是暴力法。用两个整数作为双指针构建滑动窗口，依次把每次移动后的滑动窗口的中位数求出（滑动窗口大小是偶数和奇数的情况分开讨论），存放在结果数组。不过，注意中位数是有序序列的中间数，因此，每次构造一个辅助数组复制滑动窗口的内容进行排序。

代码如下：

java">class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] ans = new double[n - k + 1];
        int l = 0, r = k - 1; //双指针指向滑动窗口两端
        int idx = 0;
        for(; r < n; r++){ //移动滑动窗口直到窗口右端抵达终点
            int[] temp = new int[k]; //构造一个辅助数组用于排序滑动窗口内容
            for(int i = 0; i < k; i++){
                temp[i] = nums[l + i];
            }
            Arrays.sort(temp); //排序
            if(k % 2 == 0){ //滑动窗口大小为偶数
                int mid = k / 2;
                ans[idx] = ((double)temp[mid] + (double)temp[mid - 1]) / 2;
            }
            else{ //滑动窗口大小为奇数
                int mid = k / 2;
                ans[idx] = temp[mid];
            }
            idx++;
            l++;
        }
        return ans;
    }
}

注意，滑动窗口大小为偶数时，中位数是中间两个数的平均值，这里要把int类型的数字做一个强制转换，变成doube，否则会造成精度丢失（例如2+3 / 2，int类型情况下等于2，doublel类型情况下等于2.5）。这种方法时间复杂度太高，偶尔还会超时。
在这里插入图片描述

暴力法耗时的一个重要原因就是每次都要对子区间进行排序，如果我们能找到一个内部本就是有序的数据结构，那么问题就能简单许多。这里不得不说要是用C++的multiset结构，那么二三十行代码就能解决问题，而且速度很快，java实现相对就要麻烦不少，~~苦逼java狗~~。

这里用java构建两个堆，一个大顶堆存放小于中位数的数字，一个小顶堆存放大于中位数的数字，那么堆顶（滑动窗口大小为奇数）或者两个堆顶的平均数（滑动窗口大小为偶数）就是中位数。注意，这个过程中需要一直控制两个堆的相对大小，要么大顶堆大小 = 小顶堆大小，要么大顶堆大小 + 1 = 小顶堆大小，这样才能保证可以一直用堆顶元素求得中位数。java实现代码如下：

java">class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] ans = new double[n - k + 1];
        PriorityQueue<Double> smallHeap = new PriorityQueue<>(); //构建小顶堆
        PriorityQueue<Double> bigHeap = new PriorityQueue<>(Collections.reverseOrder()); //构建大顶堆
        //对两个堆进行初始化，先放入第一个滑动窗口的数字
        int mid = k / 2;
        for(int i = 0; i < k; i++){
            bigHeap.add((double)nums[i]);
        }
        for(int i = mid; i < k; i++){
            smallHeap.add(bigHeap.poll());
        }
        ans[0] = k % 2 == 0 ? (bigHeap.peek() + smallHeap.peek()) / 2 : smallHeap.peek();
        for(int i = k; i < n; i++){
            double curNum = (double)nums[i]; //当前遍历到的数字
            double removeNum = (double)nums[i - k]; //当前将要移除的数字
            //若当前数字小于等于大顶堆的堆顶，则加入大顶堆，否则加入小顶堆
            if(!bigHeap.isEmpty() && curNum <= bigHeap.peek()){
                bigHeap.add(curNum);
            }
            else{
                smallHeap.add(curNum);
            }
            //若当前要移除数字小于等于大顶堆的堆顶，则从大顶堆中移除，否则从小顶堆中移除
            if(!bigHeap.isEmpty() && removeNum <= bigHeap.peek()){
                bigHeap.remove(removeNum);
            }
            else{
                smallHeap.remove(removeNum);
            }
            //控制两个堆的相对大小
            while(bigHeap.size() > smallHeap.size()){
                smallHeap.add(bigHeap.poll());
            }
            while(bigHeap.size() + 1 < smallHeap.size()){
                bigHeap.add(smallHeap.poll());
            }
            ans[i - k + 1] = k % 2 == 0 ? (bigHeap.peek() + smallHeap.peek()) / 2 : smallHeap.peek();
        }
        return ans;
    }
}