JavaScript 算法实现复写0双指针解法

段振伟

题目描述

给你一个长度固定的整数数组

1. arr

复制代码

，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。  
示例 1：

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：

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

复制代码

提示：

1. 1 <= arr.length <= 104
   
2. 0 <= arr[i] <= 9

复制代码

题解

题目表示把原数组中的零都复写一遍，看示例应该能明白什么意思，就是单纯地把原数组中为0的元素重复写一遍，复写的元素要把原索引位后面的元素往后挤一个位置出来，这样原数组中每出现一个0，新数组就将从原数组中挤掉一个末位的元素。
对比新旧两个数组，会发现新数组中的所有元素都来自旧数组，而新数组中只用到旧数组中左侧的一部分元素，如果用i来表示旧数组的索引，在遍历结束后新数组中用到的旧数组中的索引位应该是

1. 0-i

复制代码

，且

1. i<arr.length

复制代码

。也就是新数组中的指针增加到

1. arr.length - 1

复制代码

时，旧数组的指针停留在

1. i

复制代码

，这时就出现了快慢指针的场景了。
前面定义了慢指针

1. i

复制代码

，用来标记旧数组；再定义一个快指针

1. j

复制代码

，用来标记新数组。
分几步走：

• 计算出快慢指针
  
• 推算快慢指针规律
  
• 从后往前覆写旧数组
  

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

1. [0,1,2]

复制代码

>> i= 1

1. [0,0,1]

复制代码

>> j=2
例2：

1. [1,0,2,0,3]

复制代码

>> i = 3

1. [1,0,0,2,0]

复制代码

>> j = 4
例3：

1. [1,0,2,3,4]

复制代码

>> i = 3

1. [1,0,0,2,3]

复制代码

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

1. j

复制代码

是固定的就是

1. arr.length - 1

复制代码

，按这思路可以求出慢指针：

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

复制代码

算出慢指针

1. i

复制代码

的值，新数组中的元素就定好了，接下来就是把值塞进去，因为题目要求不能定义新数组，要塞进去就只能从后面塞。具体代码如下：

1. /**
   
2. * @param {number[]} arr
   
3. * @return {void} Do not return anything, modify arr in-place instead.
   
4. */
   
5. var duplicateZeros = function(arr) {
   
6.     const n = arr.length;
   
7.     let top = 0; // 新数组的极限索引
   
8.     let i = -1; // 旧数组的索引位，top到顶点时i停止
   
9.     while (top < n) {
   
10.         i++;
    
11.         if (arr[i] !== 0) {
    
12.             top++;
    
13.         } else {
    
14.             top += 2;
    
15.         }
    
16.     }
    
17.     let j = n - 1;
    
18.     if (top === n + 1) {
    
19.         // 超出原数组两个索引位，说明最后一位是0
    
20.         arr[j] = 0;
    
21.         j--;
    
22.         i--;
    
23.     }
    
24.     // i是原数组索引位，新数组只用到0-i的元素
    
25.     while (j >= 0) {
    
26.         arr[j] = arr[i];
    
27.         j--;
    
28.         // 如果当前i索引位是0，则新数组还要向后退一位且用0赋值
    
29.         if (arr[i] === 0) {
    
30.             arr[j] = arr[i];
    
31.             j--;
    
32.         }
    
33.         i--;
    
34.     }
    
35. };

复制代码

复杂度

时间复杂度：O(n)
空间复杂度：O(1)
以上就是JavaScript 算法 复写0双指针解法的详细内容，更多关于JavaScript 复写0双指针解法的资料请关注脚本之家其它相关文章！

来源:https://www.jb51.net/article/266678.htm
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！