Move Zeroes

題目:

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of Operations.

一開始的想法是，遍歷數組，遇到0就往后移，一直移動最后一步。代碼如下

public class Solution {    public static void moveZeroes(int[] nums) {        for (int i = 0; i < nums.length; i++) {            if (nums[i] == 0 && i != (nums.length - 1)) {                for (int j = i; j < nums.length - 1; j++) {                    int temp = nums[j];                    nums[j] = nums[j + 1];                    nums[j + 1] = temp;                }            }        }    }}

但是，發現001這個測試用例不對。

恩，發現問題了，因為第一個數為0，第二個0就沒辦法移動到最后了。

換一種思路，不遍歷找0，而是遍歷找非0，遇到非0，且不在第一位，就往前移，直到它前面不是0為止。

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

這樣就解決了

其他方法

public static void moveZeroes(int[] nums) {        int i = 0, j = 0;        for (i = 0; i < nums.length; i++) {            if (nums[i] != 0) {                if (j != i) {                    nums[j] = nums[i];                    nums[j] = 0;                }                j++;            }        }    }

這種方法i遍歷數組，只有當i指向為非0時，且ji不同時，j后移，將j處的數改成i處的數，并使i處的數字為0，ij同步后移，而當i指向為0時，只有i后移，j仍然指向0處。

還有一種更簡單的方法

public void moveZeroes(int[] nums) {    if (nums == null || nums.length == 0) return;            int insertPos = 0;    for (int num: nums) {        if (num != 0) nums[insertPos++] = num;    }            while (insertPos < nums.length) {        nums[insertPos++] = 0;    }}