Given an arr array of fixed length integers, each time a 0 occurs, the remaining elements are moved to the right. Elements that exceed the length of the original array are not written.

Example 1:

,0,2,3,0,4,5,0 input: [1] output: null explanation: your function call, the input array is modified into:,0,0,2,3,0,0,4 [1]Copy the code

Example 2:

Input: [1,2,3] output: null explanation: after your function call, the input array is changed to: [1,2,3]Copy the code

Note ⚠ ️ :

  • 1 <= arr.length <= 10000
  • 0 <= arr[i] <= 9

Leetcode portal: leetcode.com/problems/du…

The problem solving

Step1: let’s see how to move an element in an array first

Start with an array [1,2,3,4] and move it backwards from 0 to 1, 1 to 2, and so on… [1,1,2,3], right? Let’s put the above idea into practice and write it: [1,1,2,3]

Public class DuplicateZeros {public static void main(String[] args) {int[] arr = new int[]{1,2,3,4}; int i = 0; while (i < arr.length - 1){ arr[i+1] = arr[i]; i++; } System.out.println(Arrays.toString(arr)); } } output: [1, 1, 1, 1]Copy the code

Ah? It seems that the output is not correct. Why is that? Some basic programming should know, but LET me draw a picture to explain it

The capacity of the array is 3, and the capacity of the array is 3. The capacity of the array is 3, and the capacity of the array is 3. This prevents the previous value from overwriting the latter.

This time, let’s draw a picture to express the meaning, and then write a program

The procedure is as follows:

public class DuplicateZeros {

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

        int i = arr.length - 1;
        while (i > 0) {
            arr[i] = arr[i-1];
            i--;
        }

        System.out.println(Arrays.toString(arr));
    }
}

output:[1, 1, 2, 3]
Copy the code

Step2: Bold guess solution

Once you’ve learned how to move an array, it’s easy. Here’s what I thought:

  • Figure out the number of zeros in the array, the length of the elements in the array + the number of zeros = the number of steps to move
  • Add the step size to the calculation and take one more step when you hit 0
  • Because it’s a fixed array, the excess is discarded

Or draw a picture to express the meaning more clearly:

The solution is as follows:

class Solution { public void duplicateZeros(int[] arr) { if (arr == null || arr.length == 0) return; Int zeros = 0; for (int num : arr) { if (num == 0) { zeros++; } } if (zeros == 0) return; int len = arr.length; Int I = len-1, j = I + zeros; int I = len-1, j = I + zeros; while (i ! = j) { insert(arr, i, j--); If (arr [I] = = 0) {/ / meet 0 more step insert (arr, I, j,); } i--; }} private void insert(int[] arr, int I, int j) {if (j < arr.length) {arr[j] = arr[I]; }}}Copy the code

Step3: Confirm the conjecture

It proved our idea. It worked