Leetcode-1089: replication zero

Title Description

Give you a fixed length array of integers arr, Please copy every zero that appears in the array , And shift the rest of the elements to the right .
Be careful ： Please do not write elements beyond the length of the array .
requirement ： Please modify the input array in place , Don't return anything from a function .

Example

Example 1：
Input ：[1,0,2,3,0,4,5,0]
Output ：null
explain ： After calling the function , The input array will be modified to ：[1,0,0,2,3,0,0,4]

Example 2：
Input ：[1,2,3]
Output ：null
explain ： After calling the function , The input array will be modified to ：[1,2,3]

The problem solving process

Ideas and steps

（1） With the help of virtual arrays , The size of the virtual array is the original array  arr  identical , Variable  j  Used to record the number of array elements in a virtual array ;
（2） Use the pointer  i  To traverse the original array  arr, If  arr[i] != 0, be  i  and  j  At the same time, self increase  1, If  arr[i] == 0, Then you need to copy  0  The operation of , therefore  j  Self increasing  2,i  Self increasing  1, When  j >= arr.length  Stop traversal when ;
（3） here  i  That is, copy the original array  0  After the operation, the subscript of the last element in the virtual array will appear （ Pay attention to understanding ）;
（4） because  j  Represents the number of elements in the virtual array , Not a subscript , So we need to be right  j  Since the subtract  1  operation , Need special circumstances ： When the original array  arr  The last element of is  0  And copy  0  after  j > arr.length  了 , At this time, you need to  j  Self reduction  2, At the same time  arr[j]  The assignment is  0, Then do it again  j  Self reduction  1,i  Self reduction  1  operation ;
（5） Then copy from right to left  0  operation , If  arr[i] == 0, be  arr[j]  and  arr[j - 1]  All assigned to  0, And carry on  j  Self reduction ,2,i  Self reduction  1  operation ; If  arr[i] != 0, Will be the current  arr[i]  The value of is assigned to  arr[j], At the same time  i  and  j  Self subtraction of  1  that will do 

Code display

public class DuplicateZeros {
    

    public void duplicateZeros(int[] arr) {
    
        //  Virtual array ,  Find the last element that will appear in the virtual array ,  namely  i
        int i = 0;
        int j = 0;
        for (; i < arr.length; i++) {
    
            if (arr[i] == 0) {
    
                j += 2;
            } else {
    
                j++;
            }
            if (j >= arr.length) {
    
                break;
            }
        }
        //  Process the last element in the original array to be equal to  0  And the special case of crossing the boundary after copying 
        if (j > arr.length) {
    
            if (arr[i] == 0) {
    
                j = j - 2;
                arr[j] = 0;
                j--;
                i--;
            }
        } else {
    
            j--;
        }
        //System.out.println("i = " + i + ", j = " + j);
        //  From right to left ,  Perform replication operation 
        while (j >= 0) {
    
            arr[j] = arr[i];
            if (arr[i] == 0) {
    
                arr[j - 1] = arr[i];
                j--;
            }
            i--;
            j--;
        }
    }

    public static void main(String[] args) {
    
        int[] arr = {
    1,0,2,3,0,4,5,0};
        new DuplicateZeros().duplicateZeros(arr);
    }

}