LeetCode 283. Move Zeroes

原题链接

1. Swap leftMostZeros with non_zeros

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int N = nums.length;
        int left_zero = 0;

        for (int current = 0; current < N; current++) {
            if (nums[current] != 0) {
                if (current > left_zero) {
                    nums[left_zero] = nums[current];
                    nums[current] = 0;
                }

                left_zero++;
            }
        }

        return;
    }
}

/*
Input: [1,3,0,0,12]
cur              ^
left_0      i
Output: [1,3,12,0,0]
*/

2. Pointer of non_zeros

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int N = nums.length;
        int non_zero = 0;

        for (int current = 0; current < N; current++) {
            if (nums[current] != 0) {
                nums[non_zero++] = nums[current];
            }
            // cnotinue when current num is 0
        }

        while (non_zero <= N - 1) {
            nums[non_zero++] = 0;
        } 

        return;
    }
}

/*
1. non_zero全部放到前面去
Input: [1,3,12,3,12]
nn             ^
cur                  i
2. 剩余尾端位置都补上0
Output: [1,3,12,0,0]
*/

3. Pointer i and j

while (i < N - 1) {
    if (nums[i] == 0) {
    // move to the back
        for (int j = i + 1; j < N; j++) {
            if (nums[j] != 0) {
                swap(nums, i, j);
                break;
            }
        }
    }
    i++;
}
/*
把每个0一次一步的挪到最后一个非0的位置
效率太低了hhh
*/