「优选算法刷题」：复写零

一、题目

给你一个长度固定的整数数组?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 的元素，dest 指针后移 2 位，否则后移 1 位，而cur 指针每次后移 1 位，让 cur 指针指向最后一个非零元素，dest 指针指向最后一个元素。

这个过程需要处理一下临界情况，也就是避免 dest 指针越界的情况发生。

最后的复写操作，其实类似前一步，遇到值为 0 的元素，dest 指针前移 2 位，否则前移 1 位，而cur 指针每次后移 1 位；同时，值不为 0 的元素，则把 cur 指针的元素赋给 dest 指针。

三、完整代码

public class Solution {

    public void duplicateZeros(int[] arr) {
        int cur = 0 ,  dest = -1;

        //找到最后一个非零元素
        while ( cur < arr.length) {
            if (arr[cur] == 0){
                dest+=2;
                }else {
                dest++;
                }
                if(dest >= arr.length-1){
                    break;
                }
                cur++;
            }

        //处理临界情况
        if (dest == arr.length) {
            arr[arr.length - 1] = 0;
            cur--;
            dest -= 2;
        }

        //复写操作
        while(cur >= 0) {
            if (arr[cur]!=0){
                arr[dest--]=arr[cur--];
            }else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }


    }
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！