优选算法|【双指针】|1089.复写零

题目描述

1089. 复写零

给你一个长度固定的整数数组 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，其他元素向右平移就行。只能在原来数组上修改，也就是空间复杂度为0.

算法原理讲解

       一般像这种在数组中移动一些数的题目，也是用双指针算法来解决这个问题。

      双指针算法是根据异地解法的操作，优化成双指针的就地操作。

异地操作

异地操作就是，重新开辟一个数组。

       定义两个指针，cur用来扫描原数组，dest用来更新新数组。

       当cur对应的值不等于0时，dest更新一个数，将cur值直接填入dest的位置，dest++，cur++就行。

       当cur对应的值等于0时，dest指针更新两个数，都填入0,cur++就行。

       当dest=arrSize就结束了。

就地操作

       就是不用重新开辟数组，也就是题目要求的那样，我们可以把cur和dest这两个指针，都放在原数组上。

      用双指针解决复写问题的步骤

1.找到最后一个复写的数

2.从后向前完成复写

       让cur指向最后一个复写的数，对于[1,0,2,3,0,4,5,0]这个数组，最后一个复写的数是4，所以让cur指向4 ，best指向最后一个位置就行。

cur指向的这个数是非零的，所以复写一次就行，复写完后，cur--,dest--。

这次cur指向0，那就复写两次，后cur--。

从图中可以看出，当cur和dest都指向-1的时候就复写完成了。

接下来有一个问题就是？——怎么找到最后一个复写的数

       还是利用双指针算法，定义两个指针cur和dest,cur用来扫描数组，dest用来标识最后一个复写的数。

cur指向的值决定dest向后移动两步还是移动一步

1.先判断cur里面的值

2.决定dest走两步还是走一步

3.在判断dest到没到结尾

4.没到结尾再cur++

       咱们一步一步来，arr[cur]现在指向了1，所以dest走一步到达下标为0的位置，dest没有走到结尾，所以cur++。

arr[cur]现在指向了0，所以dest走两步到达下标为2的位置，dest没有走到结尾所以cur++。

arr[cur]现在指向了2，所以dest走一步到达下标为3的位置，dest没有走到结尾所以cur++。

arr[cur]现在指向了3，所以dest走一步到达下标为4的位置，dest没有走到结尾所以cur++。

arr[cur]现在指向了0，所以dest走两步到达下标为6的位置，dest没有走到结尾所以cur++。

arr[cur]现在指向了4，所以dest走一步到达下标为7的位置，dest走到结尾返回cur。

       对于这个数组这种方法是刚好的，那么如果是【1，0，2，3，0，4】

arr[cur]现在指向了1，所以dest走一步到达下标为0的位置，dest没有走到结尾所以cur++。

arr[cur]现在指向了0，所以dest走两步到达下标为2的位置，dest没有走到结尾所以cur++。

arr[cur]现在指向了2，所以dest走一步到达下标为3的位置，dest没有走到结尾所以cur++。

arr[cur]现在指向了3，所以dest走一步到达下标为4的位置，dest没有走到结尾所以cur++。

        arr[cur]现在指向了0，所以dest走两步到达下标为6的位置，但是这个数组没有下标6最大直到5,所以会产生越界。

       接下来，我们怎么解决这个问题，我们要明白越界是怎么产生的，是因为复写0,复写两次就产生了越界。这个情况我们单独处理一下。

那么怎么处理呢？我们在复写的时候将最后一个位置，和越界的那个位置都复写成0。但是越界那个位置不能修改成0，我们只需要把最后一个位置修改成0（直接在这里复写），也就是arr[arrSzie-1]=0,就可以。

修改之后我们将dest向前移动两步，cur向前移动一步

cur现在就是最后一个复写的值，接下来复写就从dest现在的位置开始复写。

代码

void duplicateZeros(int* arr, int arrSize) {
    //找到最后一个复写的位置
    int cur=0;
    int dest=-1;
    while(cur<arrSize)
    {
        if(arr[cur]==0)dest+=2;
        if(arr[cur]!=0)dest+=1;
        //如果dest到达最后一个位置就跳出循环
        //如果刚好的话是等于arrSzie-1，有越界的时候是等于arrSize
        if(dest==arrSize-1||dest==arrSize)break;
        cur++;
    }
    //处理边界
    if(dest==arrSize)
    {
        arr[arrSize-1]=0;
        cur-=1;
        dest-=2;
    }
    while(cur>=0&&dest>=0)
    {
        if(arr[cur]==0)
        {
            arr[dest--]=arr[cur];
            arr[dest--]=arr[cur--];
        }
        else
        {
            arr[dest--]=arr[cur--];
        }
    }
    
}