【LeetCode】每日一题 1089题复写零：利用左右双指针确定截断位置，再依次进行原地修改一、基本思路二、代码实现分析：运行结果：

83 阅读 0 评论 55 点赞

我是靠谱客的博主风中电话，这篇文章主要介绍【LeetCode】每日一题 1089题复写零：利用左右双指针确定截断位置，再依次进行原地修改一、基本思路二、代码实现分析：运行结果：，现在分享给大家，希望可以做个参考。

文章目录

一、基本思路
二、代码实现
分析：
运行结果：

一、基本思路

（1）对于长度为n的数组在i位置遇到0就要在该位置的后面插入一个0，则等价于先将i+1至n-1视为整体，将其向后移动1个位置，整体坐标变为i+2至n,由于数组大小不可变，则将应将尾部元素舍弃，如下图所示：在这里插入图片描述
（2）因此可以利用左右双指针来确定总共需要舍弃几个元素，即找到截断的位置，具体做法为：
1.初始化左右指针：left = 0， right = arr.length;
2.当arr[left] == 0 时，可以明确此时需要从尾部舍弃一个元素，则令 right–，即将右指针指向需要舍
弃的元素;
3.当left >= right时，此时右指针right所指向的位置到数组尾部均为需要舍弃的元素，此时再将right依次向前移动，将其指向的元素值赋值到数组尾部即可。其中需要注意的是当 left > right 时，此时表示 right 所指向的元素应当保留，需要进行单独处理,读者可对数组{8,4,5,0,0,0,7}进行模拟即可明确此特殊情况~;
幻灯片2.PNG 幻灯片3.PNG 幻灯片4.PNG 幻灯片5.PNG 幻灯片6.PNG 幻灯片7.PNG 幻灯片8.PNG 幻灯片9.PNG 幻灯片10.PNG 幻灯片11.PNG 幻灯片12.PNG 幻灯片13.PNG 幻灯片14.PNG 幻灯片15.PNG 幻灯片16.PNG 幻灯片17.PNG

二、代码实现

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public void duplicateZeros(int[] arr) {
        if (arr.length == 0)
            return;

        int left = 0;
        int right = arr.length;

        while (left < right){
            if (arr[left] == 0){
                right--;
            }
            left++;
        }

        int index = arr.length-1;
        if (right < left){ // 此时表示right所指向的元素应当保留，需要进行单独处理；
            arr[index--] = arr[right--];
        }else {
            right--;
        }
        while (right >= 0){
            if (arr[right] != 0){
                arr[index--] = arr[right];
            }else {
                arr[index--] = 0 ;
                arr[index--] = 0;
            }
            right--;
        }
    }
}