283. Move Zeroes

Question

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]

Follow up

Could you minimize the total number of operations done?

Algorithm

1. Basic solution is to leverage bubble sort and bubble the 0 to the end, this will have a O(n*n) time complexity;
2. In the follow up, the algorithm is showed in the second code part, we maintain two pointers, one is normal index for looping, the other is the sorted or moved numbers' end, so
   1. each time the nums[index] == 0, we can put into the nums[sortedEnd], because the sorted is slower than the normal index.
   2. Then after all the numbers are put into previous part as non-zero part, the numbers after sorted end should be set all zero.
   3. This is a O(n) solution whose operation number is less.

Code

class Solution {
    public void moveZeroes(int[] nums) {
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == 0) {
                for (int j = i; j < nums.length - 1; j++) {
                    if (nums[j + 1] != 0) swap(nums, j, j + 1);
                    else break;
                }
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int start = 0;
        int index = 0;
        while (index < nums.length) {
            if (nums[index] != 0) {
                nums[start++] = nums[index];
            }
            index++;
        }
        while (start < nums.length) nums[start++] = 0;
    }
}