283. Move Zeroes

[songyy5517]

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Analysis The problem mainly examines the operations of arrays. To move all the zeros to the end of the array, we can have this idea: move all non-zero numbers to the left, and all zeros to the right. Specifically, we can iterate through the whole array, and record the number of zeros at present. If the present element is zero, then just update the number of zeros; If the present element is non-zero, then we need to move it to the left non-zero part, so swap the first zero with the current number.

[songyy5517]

Approach: Two pointers & Travarsal once

1. Exception handling;
2. Define variables:
   • zeros: record the number of continuous zeros before;
3. Loop through the whole array: （1）If the present element is 0, then add 1 to zeros; （2）If the present element is non-zero, just swap this element with the first zero before.
4. Return;

Complexity Analysis

• Time complexity: $O(N)$ , looping through the array once takes the time of $O(N)$ ;
• Space complexity: $O(1)$ , additionally define constant-level variables.

[songyy5517]

class Solution {
    public void moveZeroes(int[] nums) {
        // Intuition: Travarse the array.
        // 1. Exception handling
        if (nums == null || nums.length == 0)
            return ;

        // 2. Define two pointers
        int zero = 0;    // record the number of zeros before the current number

        // 3. Loop through the array
        for (int i = 0; i < nums.length; i++){
            // the current number is 0
            if (nums[i] == 0)
                zero ++;

            // there are zeros before the current number, then put the current number before the zeros.
            else if (zero > 0) {    
                nums[i - zero] = nums[i];
                nums[i] = 0;
            }
        }

        return;
    }
}

[songyy5517]

2024/5/10