×

JavaScript每日一学:JavaScript 算法实现复写0双指针解法

作者:Terry2023.01.13来源:Web前端之家浏览:268评论:0
关键词:js

JavaScript每日一学:JavaScript 算法实现复写0双指针解法。

给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。

注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。  

示例 1:

输入: arr = [1,0,2,3,0,4,5,0]
输出: [1,0,0,2,3,0,0,4]
解释: 调用函数后,输入的数组将被修改为:[1,0,0,2,3,0,0,4]

示例 2:

输入: arr = [1,2,3]
输出: [1,2,3]
解释: 调用函数后,输入的数组将被修改为:[1,2,3]

提示:

1 <= arr.length <= 104

0 <= arr[i] <= 9

题解

题目表示把原数组中的零都复写一遍,看示例应该能明白什么意思,就是单纯地把原数组中为0的元素重复写一遍,复写的元素要把原索引位后面的元素往后挤一个位置出来,这样原数组中每出现一个0,新数组就将从原数组中挤掉一个末位的元素。

对比新旧两个数组,会发现新数组中的所有元素都来自旧数组,而新数组中只用到旧数组中左侧的一部分元素,如果用i来表示旧数组的索引,在遍历结束后新数组中用到的旧数组中的索引位应该是0-i,且i<arr.length。也就是新数组中的指针增加到arr.length - 1时,旧数组的指针停留在i,这时就出现了快慢指针的场景了。

前面定义了慢指针i,用来标记旧数组;再定义一个快指针j,用来标记新数组。

分几步走:

  • 计算出快慢指针

  • 推算快慢指针规律

  • 从后往前覆写旧数组

这里主要讲下规律,如果实在不行,可以举例推演:

例1:

[0,1,2] >> i= 1

[0,0,1] >> j=2

例2:

[1,0,2,0,3] >> i = 3

[1,0,0,2,0] >> j = 4

例3:

[1,0,2,3,4] >> i = 3

[1,0,0,2,3] >> j = 4

基本上我可以靠人肉智能直接写出来,从左往右,非零直接写,遇到0写两遍,直到栈顶。例2和例3的快慢指针是一样的,他们区别的点是最后一个元素,一个是0一个不是0。如果定义一个变量,按照前面人肉智能的逻辑,用来表示旧数组的元素要在新数据写的次数之和t,这个区别就出来了:第一个是3,第二个是6(后面的一个0没位置了),第三个是5。最后一个数要么是0,要么不是0,如果是0,t肯定比arr.length大1。

其实快指针的值j是固定的就是arr.length - 1,按这思路可以求出慢指针:

const n = arr.length;
let top = 0; // 新数组不计溢出时需要添加的个数
let i = -1; // 旧数组的索引位,top到顶点时i停止
while (top < n) {
    i++;
    if (arr[i] !== 0) {
        top++;
    } else {
        top += 2;
    }
}

算出慢指针i的值,新数组中的元素就定好了,接下来就是把值塞进去,因为题目要求不能定义新数组,要塞进去就只能从后面塞。具体代码如下:

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function(arr) {
    const n = arr.length;
    let top = 0; // 新数组的极限索引
    let i = -1; // 旧数组的索引位,top到顶点时i停止
    while (top < n) {
        i++;
        if (arr[i] !== 0) {
            top++;
        } else {
            top += 2;
        }
    }
    let j = n - 1;
    if (top === n + 1) { 
        // 超出原数组两个索引位,说明最后一位是0
        arr[j] = 0;
        j--;
        i--;
    } 
    // i是原数组索引位,新数组只用到0-i的元素
    while (j >= 0) {
        arr[j] = arr[i];
        j--;
        // 如果当前i索引位是0,则新数组还要向后退一位且用0赋值
        if (arr[i] === 0) {
            arr[j] = arr[i];
            j--;
        } 
        i--;
    }
};

复杂度

时间复杂度:O(n)

空间复杂度:O(1)

您的支持是我们创作的动力!
温馨提示:本文作者系Terry ,经Web前端之家编辑修改或补充,转载请注明出处和本文链接:
https://www.jiangweishan.com/article/js20230113a1.html

网友评论文明上网理性发言 已有0人参与

发表评论:

最新留言

  • jianj

    node看上有点复杂...

  • 访客

    正好遇到,谢谢分享...

  • jimmy

    这个很有趣,国内SEO更多的是百度...

  • jenny

    VUE的总结的不错啊,收藏了。下次搞点React的啊...

  • jenny

    win7最经典,想当初win8出来后都没它好用,怀恋经典。。。...

  • Terry

    谢谢提醒,插件已经修复。...

  • 访客

    士大夫士大夫...

  • 访客

    用這甚麼顏色...

首页|JavaScript|HTML|HTML4|HTML5|CSS3|开发工具|性能优化|移动开发|前端教程|性能优化|开发工具|酷站欣赏|UI设计|前端教程

Copyright © 2023 Web前端之家(www.jiangweishan.com) 版权所有 All Rights Reserved.
粤ICP备12067512号-1

Copyright Your WebSite.Some Rights Reserved.

Powered By Z-BlogPHP 1.7.2