LeetCode热题100-283.移动零

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

示例 2:

输入: nums = [0] 输出: [0]

进阶：你能尽量减少完成的操作次数吗？

题解思路-双指针：

使用两个指针 i 和 j 。i 负责遍历整个数组，在遍历数组的时候，j 用来记录当前所有非0元素的个数。遍历的时候每遇到一个非0元素就将其往数组左边挪，挪动到 j 所在的位置，注意是挪动，不是交换位置，j 同时也移动一个位置。当第一次遍历完后，j 指针的下标就指向了已经排完了位置的最后一个非0元素下标。 进行第二次遍历的时候，起始位置就从 j 开始到结束，将剩下的这段区域内的元素全部置为0即可。

时间复杂度是O(n)，空间复杂度则变为O(1)。

代码实现：

▼
Java
复制代码
    /*双指针方式实现*/
    public void moveZeroes(int[] nums) {
        if(nums==null) {
            return;
        }
        //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
        int j = 0;
        for(int i=0;i<nums.length;++i) {
            if(nums[i]!=0) {
                // j++ 先赋值再加加
                nums[j++] = nums[i];
            }
        }
        //非0元素统计完了，剩下的都是0了
        //所以第二次遍历把末尾的元素都赋为0即可
        for(int i=j;i<nums.length;++i) {
            nums[i] = 0;
        }
    }

▼
Java
复制代码
    /*双指针方式实现，但是取消了第二次循环*/
    public static void moveZeroes(int[] nums){
        if(nums==null) {
            return;
        }
        int j =0;
        for (int i = 0; i < nums. length; ++i) {
            if (nums[i] != 0){
                nums[j] = nums[i];
                if (i != j) {
                    nums[i] = 0;
                }
                j++;
            }
        }
    }

▼
Java
复制代码
    /*一次遍历,快速排序的思想*/
    public static void moveZeroes2(int[] nums) {
        if(nums==null) {
            return;
        }
        //两个指针i和j
        int j = 0;
        for(int i=0;i<nums.length;i++) {
            //当前元素!=0，就把其交换到左边，等于0的交换到右边
            if(nums[i]!=0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }