LeetCode--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.

Example:

Input:[0,1,0,3,12] Output:[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的元素移动至数组尾部，不能影响数组中原非0元素的相对位置。

方法一：遍历数组，遇到0则将后面所有位置元素前移，并在末尾处补0，时间复杂度O(n2)

public void moveZeroes(int[] nums) {
    int cnt = 0;
    for(int i = 0 ; i < nums.length - cnt; ){
        if(nums[i] == 0){
            for(int j = i+1 ; j < nums.length - cnt; j++){
                nums[j-1] = nums[j];
            }
            nums[nums.length - 1 - cnt] = 0;
            cnt ++;
        }else{
            i ++;
        }
    }
}

方法二：O(n)解法，

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