keep move！滑动窗口中位数与滑动魔方

2022 年 9 月 30 日
广东
本文字数：2190 字
阅读完需：约 7 分钟

即使都是窗口滑动，但“怎么滑”，滑动后“怎么做”，里面就存在很大的解题思路的差异！

本篇继续来探索、发现、记录这个差异~ 当然也不能忘了解题中的感受分享~

滑动窗口中位数

题目：给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

中位数：

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数，例如：
[2,3,4]，中位数是 3[2,3]，中位数是 (2 + 3) / 2 = 2.5

复制代码

示例：

给出 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]

复制代码

有了前面两篇文章的基础，老观众肯定知道：此题解题的关键肯定不在于窗口滑动，而在于“滑动的过程中怎么去求这个中位数？”

暴力求解：

// 计算中位数---奇数情况function calMedianOdd(sortedWindow) {    const len = sortedWindow.length;    return sortedWindow[Math.floor(len / 2)];}// 计算中位数---偶数情况function calMedianEven(sortedWindow) {    const len = sortedWindow.length;    return (sortedWindow[Math.floor(len / 2)] +        sortedWindow[Math.floor(len / 2) - 1]) / 2;}

复制代码

不出意外，会报错：超出时间限制，因为每次发生窗口滑动了，还要进行排序，时间复杂度大于 O(n * k)，还取决于排序算法；

那有没有什么办法在滑动窗口的时候能利用上一个滑窗的状态？

答案肯定是“有的”，不然到这就剧终了~

有一个很重要的条件不能忽略：每次移动时，在删除左边界元素与加入右边界元素之前，窗口内的内容必然有序；

所以，在我们初始化排完顺序之后，发生第一次窗口的滑动时，希望找到右边界元素插入的正确位置（splice），以保障插入后直接就是有序的了，不用再排序了；

于是乎：问题变成了 —— 在有序数列中找到一个位置，于是乎，【二分法】登场！

// 二分搜索function binarySearch(sortedArr, target) {    // 这里的搜索区间是左闭右开    let left = 0;    let right = sortedArr.length;    while (left < right) {        const mid = Math.floor((left + right) / 2);        // 不能舍去mid        if (sortedArr[mid] > target) {            right = mid;        } else if (sortedArr[mid] <= target) {            left = mid + 1;        }    }    return right;}

复制代码

完整算法就不贴了，思路已经有了，具体实现就自己敲敲打打吧~

小结：滑动窗口的重点不是使窗口滑动就完事了，重点是下一窗口的滑动怎样利用上一窗口的“特性”，比如：有序；

滑动魔方

题目：在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

示例：

输入：board = [[1,2,3],[4,0,5]]输出：1解释：交换 0 和 5 ，1 步完成
输入：board = [[1,2,3],[5,4,0]]输出：-1解释：没有办法完成谜板
输入：board = [[4,1,2],[5,0,3]]输出：5解释：最少完成谜板的最少移动次数是 5 ，一种移动路径:尚未移动: [[4,1,2],[5,0,3]]移动 1 次: [[4,1,2],[0,5,3]]移动 2 次: [[0,1,2],[4,5,3]]移动 3 次: [[1,0,2],[4,5,3]]移动 4 次: [[1,2,0],[4,5,3]]移动 5 次: [[1,2,3],[4,5,0]]

复制代码

哇，这个读完题就能感觉到难度，有点像是玩魔方，把一个数组丢到一个算法里进行“旋转”，最后得出一共走了几步；

解题关键词：广度优先搜索（BFS）；

直白来说就是穷举，每走一步，列出所有变化，然后与目标值匹配，如果没有，再多走一步，然后再穷举、匹配，搜索完成后，还没有匹配的，则返回 -1；

本题当中，由于是一个二维数组，所以，注意条件是 与一个相邻的数字（上下左右）进行交换 ；

例如 0 所在的位置是 x，对于每一个与 x 相邻的位置 y，我们将 status[x] 与 status[y] 进行交换，即等同于进行了一次操作；

关键代码：

...// 枚举 status 通过一次交换操作得到的状态    const get = (status) => {        const ret = [];        const array = Array.from(status);        const x = status.indexOf('0');        for (const y of neighbors[x]) {            [array[x], array[y]] = [array[y], array[x]];            ret.push(array.join(''));            [array[x], array[y]] = [array[y], array[x]];        }        return ret;    }...

复制代码

其实本题还有另一种思路：在很久前写过一篇《狄克斯特拉算法》，能给到一些启发~~ (●'◡'●) BFS，yyds!

<hr>

OK，至此，我们前前后后通过滑动窗口认识了：单调队列、二分法、广度优先搜索；

有一说一，滑动窗口，有点东西！！

我是掘金安东尼，公众号同名，输出暴露输入，技术洞见生活，下次再会~~

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/458ccd70a2a0b22d1b102da8d】。文章转载请联系作者。

掘金安东尼

关注

安东尼陪你度过漫长编程岁月~ 2022.07.14 加入

真正的大师，永远怀着一颗学徒的心（易）

发布

暂无评论

创作场景

keep move！滑动窗口中位数与滑动魔方

滑动窗口中位数

滑动魔方

掘金安东尼

评论