CONY的世界

283. 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:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

這篇算是紀念一下自己可以把簡單的寫法想的很難

一開始用了insertion sort 的概念，去記錄最後一個不為0的值，然後只要發現中間有0而再遇到一個不為0的值就swap （if nonzero+1 != index)

class Solution {
    public void moveZeroes(int[] nums) {
        int nonzero = -1;
        for(int index =0; index < nums.length; index++){
            if(nums[index] != 0) {
                nonzero++;
                if(nonzero != index)
                    swap(nums, nonzero,index);                
            }
        }
    }
    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

但是其實這題可以不用這麼麻煩，其實只要把不為0的值留下或是複寫到最後不為0值的下一個位置就可以了

某種程度來說就是我其實不需要真的做出swap function，因為這邊只換0的關係 

class Solution {
    public void moveZeroes(int[] nums) {
        int nonzero=0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] != 0){
                if(i > nonzero) {
                    nums[nonzero] = nums[i];
                    nums[i] = 0;
                }
                nonzero++;
            }
        }            
    }
}