【每日一题】 480. 滑动窗口中位数

淩亂°似流年 2022-10-30 11:19 140阅读 0赞

# 【每日一题】 480. 滑动窗口中位数 #

> 避免每日太过咸鱼，一天搞定一道LeetCode算法题

## 一、题目描述 ##

难度： **困难**

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

例如：

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

**提示：**

*  你可以假设 `k` 始终有效，即：`k` 始终小于输入的非空数组的元素个数。
 *  与真实值误差在 `10 ^ -5` 以内的答案将被视作正确答案。

**示例 1：**

给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
    窗口位置                      中位数
    ---------------               -----
    [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
    因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

## 二、题解 ##

### 1. 解法 ###

### **解题思路：** ###

不要把问题想得太复杂，二分查找+冒泡排序完全可以解决

*  维护一个排过序的滑动窗口数组
 *  使用二分查找检索删除的索引
 *  将需要删除的值替换为需要插入的值
 *  使用局部冒泡排序保证数组顺序

**代码**

public double[] medianSlidingWindow(int[] nums, int k) { 
        double[] res = new double[nums.length - k + 1];
        int[] window = new int[k];
        //添加初始值
        for (int i = 0; i < k; i++) { 
            window[i] = nums[i];
        }
        //初始的快排，懒得写直接调用
        Arrays.sort(window);
        res[0] = getMid(window);
        //窗口滑动
        for (int i = 0; i < nums.length - k; i++) { 
            //需要删除的数
            int index = search(window, nums[i]);
            //替换为需要插入的数
            window[index] = nums[i + k];
            //向后冒泡
            while (index < window.length - 1 && window[index] > window[index + 1]) { 
                swap(window, index, index + 1);
                index++;
            }
            //向前冒泡
            while (index > 0 && window[index] < window[index - 1]) { 
                swap(window, index, index - 1);
                index--;
            }
            res[i + 1] = getMid(window);
        }
        return res;
    }
    
    //交换
    private void swap(int[] window, int i, int j) { 
        int temp = window[i];
        window[i] = window[j];
        window[j] = temp;
    }
    
    //求数组的中位数
    private double getMid(int[] window) { 
        int len = window.length;
        if (window.length % 2 == 0) { 
            //避免溢出
            return window[len / 2] / 2.0 + window[len / 2 - 1] / 2.0;
        } else { 
            return window[len / 2];
        }
    }
    
    //最简单的二分查找
    private int search(int[] window, int target) { 
        int start = 0;
        int end = window.length - 1;
        while (start <= end) { 
            int mid = start + (end - start) / 2;
            if (window[mid] > target) { 
                end = mid - 1;
            } else if (window[mid] < target) { 
                start = mid + 1;
            } else { 
                return mid;
            }
        }
        return -1;
    }

题目来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/distance-between-bus-stops

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: /images/20221024/7e62c122313c43fba97dc8c1aa3ecf3d.png