letcode刷题n13-q283：移动零

这是我参与11月更文挑战的第16天，活动详情查看：2021最后一次更文挑战

题目描述

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

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
通过次数536,652提交次数838,302

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路 & CODE

这种题如果想要在原数组上操作一般都要使用到双指针。

1. 快慢指针

创建两个指针fast和slow

慢指针指向为0的元素，快指针寻找慢指针之后的非0元素，用来覆盖慢指针所在位置的元素

• 开始时，两指针都指向数组头，如果nums[slow]不为0，则slow++，fast++
• 如果nums[slow]为0，则fast++，直到fast找到不为0的元素覆盖slow位置，此时需要使用while循环找到一个首先小于等于fast索引位置且nums[slow]=0的位置赋值给slow，如果找不到就让slow=fast
• 如此循环到结束数组就处理好了

代码如下：

public void moveZeroes(int[] nums) {
    int slow = 0;
    int fast = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[slow] != 0) {
            slow++;
            fast++;
        } else {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                nums[fast] = 0;
                while (slow <= fast && nums[slow] != 0) {
                    slow++;
                }
            }
            fast++;
        }
    }
}
复制代码

虽然代码通过了，但是这段代码却显得很臃肿，和我刚开始的想法有出入。

刚开始想的是，不管nums[slow]是不是0，都可以用同样的代码处理，不需要分类讨论，也就是说slow和fast可以同时移动不需要用if else来判断。但是写着写着就走远了。

看了眼官方题解就是我的版本的精简版，且看代码

public void moveZeroes(int[] nums) {
    int n = nums.length, left = 0, right = 0;
    while (right < n) {
        if (nums[right] != 0) {
            swap(nums, left, right);
            left++;
        }
        right++;
    }
}

public void swap(int[] nums, int left, int right) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}
复制代码

可以看到这里通过对right的控制达到了同时移动left和right的目的

• 开始时left=right，只要right不为0，left就和right同时移动
• 当right等于0，right还是一样移动，应为if (nums[right] != 0)这个条件满足left才会移动，所以此时left不动，并且left指向0。
• 当right不为0，right和left就会值替换，然后left往后移动一格
• 循环结束数组排序完成

总结

以后遇到双指针的题目，考虑只使用右指针来控制两个指针的移动

2. 双指针补零

用双指针也是有不同的写法滴

这种办法其实和上面相似，都是靠判断右指针来移动两个指针，不同的是这里直接让右指针的元素覆盖左指针的元素，最后补0

理解的关键点就在：最初左右指针指向同一个位置，即使覆盖了值，他们的指向还是相同的，只有遇到零时，两个指针的相对位置才会发生改变

public void moveZeroes2(int[] nums) {
    int count = 0;
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            nums[slow++] = nums[fast];
            count++;
        }
    }
    while (count < nums.length) {
        nums[count++] = 0;
    }
}
复制代码