为什么不建议学python（JavaScript 算法实现复写0双指针解法）

时间2025-09-18 17:22:47分类IT科技浏览6101

导读：题目描述给你一个长度固定的整数数组arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。...

题目描述

给你一个长度固定的整数数组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 ，按这思路可以求出慢指针：

算出慢指针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)

以上就是JavaScript 算法复写0双指针解法的详细内容，更多关于JavaScript 复写0双指针解法的资料请关注本站其它相关文章！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。