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

举报
掘金安东尼 发表于 2022/09/30 10:04:42 2022/09/30
【摘要】 即使都是窗口滑动,但“怎么滑”,滑动后“怎么做”,里面就存在很大的解题思路的差异!本篇继续来探索、发现、记录这个差异~ 当然也不能忘了解题中的感受分享~ 滑动窗口中位数题目:给你一个数组 nums,有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数,每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数,并输出由它们组成的数组。中位数:中位数是有序序列...

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

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

滑动窗口中位数

题目:给你一个数组 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
解释:交换 051 步完成

输入: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;

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

image.png

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


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

有一说一,滑动窗口,有点东西!!

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。