描述

給一個(gè)數(shù)組 nums 寫(xiě)一個(gè)函數(shù)將 0 移動(dòng)到數(shù)組的最后面，非零元素保持原數(shù)組的順序

注意事項(xiàng)

1.必須在原數(shù)組上操作
2.最小化操作數(shù)

樣例

給出 nums = [0, 1, 0, 3, 12], 調(diào)用函數(shù)之后, nums = [1, 3, 12, 0, 0].

知識(shí)點(diǎn)

相向，同向型兩根指針一直往前走，時(shí)間復(fù)雜度都為 O(n)，若左指針前進(jìn)一步右指針回到初始位置重新走的話時(shí)間復(fù)雜度為 O(n^2),兩根指針一般用在 O(n) 的時(shí)間復(fù)雜度，要比 O(nlogn) 快

思路

用同向型指針，一個(gè)指向第一個(gè)為 0 的元素，一個(gè)指向第一個(gè)不為 0 的元素， 在向右移動(dòng)過(guò)程中不斷把 0 交換到數(shù)組的末尾

代碼

1. 統(tǒng)計(jì)數(shù)組中 0 的個(gè)數(shù)，把不為 0 的數(shù)按照順序全部加入到動(dòng)態(tài)數(shù)組中，然后在按照統(tǒng)計(jì)個(gè)數(shù)把 0 加入，最后用數(shù)組復(fù)制下動(dòng)態(tài)數(shù)組中的元素，時(shí)間復(fù)雜度 O(n) 空間復(fù)雜度 O(n)

public class Solution {
    /*
     * @param nums: an integer array
     * @return: 
     */
    public void moveZeroes(int[] nums) {
        int count = 0;
        ArrayList<Integer> array = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                array.add(nums[i]);
            } else {
                count++;
            }
        }
        
        while (count-- != 0) {
            array.add(0);
        }
        
        for (int i = 0; i < nums.length; i++) {
            nums[i] = array.get(i);
        }
    }
}

2. 遍歷過(guò)程中直接把非 0 數(shù)全拷貝到 nums 數(shù)組中，后面空位全部補(bǔ) 0，時(shí)間復(fù)雜度 O(N)，空間復(fù)雜度 O(1)
   不存在非 0 數(shù)被覆蓋的情形，0 被覆蓋，非 0 數(shù)停留在原地

public class Solution {
    /*
     * @param nums: an integer array
     * @return: 
     */
    public void moveZeroes(int[] nums) {
        int lastNoZeroIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[lastNoZeroIndex++] = nums[i];
            }
        }
        
        for (int i = lastNoZeroIndex; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

3. 上一種的時(shí)間復(fù)雜度在遍歷完一遍數(shù)組后又遍歷了 0 的個(gè)數(shù)，用兩根指針優(yōu)化時(shí)間復(fù)雜度，讓算法只遍歷一遍數(shù)組，時(shí)間復(fù)雜度 O(N)，空間復(fù)雜度 O(1)
   AAA000BC ————> AAAB000C
   left 始終指向第一個(gè)0只是下標(biāo)在移動(dòng)，right 剛開(kāi)始指向 B，交換完后后移一位指向 C，始終是指向第一個(gè)非 0 數(shù)

public class Solution {
    /*
     * @param nums: an integer array
     * @return: 
     */
    public void moveZeroes(int[] nums) {
        // left 代表數(shù)組中第一個(gè)值為 0 的下標(biāo)
        // right 代表數(shù)組中第一個(gè)值不為 0 的下標(biāo)
        int left = 0, right;
        for (right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                /* 在沒(méi)遇到第一個(gè) 0 之前，right 每移動(dòng)一次 left 也跟著移動(dòng)，
                 * left 和 right 始終指向同一元素，交換也是自己和自己的交換，
                 * 所以不會(huì)出現(xiàn)如果數(shù)組第一個(gè)元素不是 0，right++跑到 0，
                 * 而 left 仍在數(shù)組第一個(gè)元素處不動(dòng)的反向交換情形
                 */
                left++;
            }
        }
    }
}