移动零

2017-09-15

From : www.LintCode.com

描述
给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序。

注意
1.必须在原数组上操作
2.最小化操作数

样例
给出nums = [0, 1, 0, 3, 12]，
调用函数之后, nums = [1, 3, 12, 0, 0].

解决方案一

此题与LeetCode中的一题很相似。参见Remove Element
解决思路：
首先，定义一个标记index，来标记非0数存放的位置。
然后，遍历数组，将所有的非0数都放在index所标记的位置，
每放一个元素，index标记后移一位。
遍历结束后，将index及index之后的元素全部置0。

代码实现（JAVA）

public class Solution {
    /*
     * @param nums: an integer array
     * @return:
     */
    public void moveZeroes(int[] nums) {
        // write your code here
        //定义索引，用来标记非0数存放的位置
        int index = 0;
        //遍历数组
        for (int j = 0; j < nums.length; j++) {
            //若当前元素非0
            if (nums[j] != 0) {
                //则将该元素放在index标记的位置
                nums[index] = nums[j];
                //并将index标记后移一位
                index++;
            }
        }
        //将index之后的元素全部置0
        for (int k = index; k < nums.length; k++){
            nums[k] = 0;
        }
    }
}

总结

1、index的移动速度小于等于遍历数组的速度。
最坏的情况下，非0元素全部都在数组的前面，此时index的移动速度和遍历数组的速度相同，也就是说，此时元素并没有交换（或者说自己跟自己交换，因为二者移动速度相同，说明index的值等于j的值）。除此之外，index的速度都要小于数组遍历的速度。
2、本题与Remove Element 的不同之处在于，Remove Element 只要求将非val元素放在前面，val元素不考虑，因此不存在最后的赋值步骤。
而本题要求将非0数放在前面，而将0放在后面，因此需要将最后的元素全部置0。