【LC75】No283. 移动零

题目描述

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

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

提示:

• 1 <= nums.length <= 10⁴

• -2³¹ <= nums[i] <= 2³¹ - 1

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

示例

示例 1:

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

示例 2:

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

链接

思路

依旧是很好理解的题目，没有背景设置，所以中译中环节省略。

注意题目中的一点要求，在不复制数组的情况下对原数组进行操作。

解法一：非零前移，末尾补0

数组中非 0 和 0 交替出现，我们最先可以想到最简单的办法是，将每个 0 后的数字前移，然后在结尾补 0 填充完整个数组。

代码

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

• 时间复杂度：O(n)

• 空间复杂度：O(1)

解法二：双指针

解法一使用了两次遍历，那么我们可以优化在一次遍历中完成吗？

解题需要我们分别找到 0 和 后面的非 0，然后进行交换，对于这个思路，很容易想到快慢指针。

定义一个慢指针 left，让它永远指向数组从左开始的第一个 0；定义一个快指针 right，让它作为循环遍历的标识。

当快指针 right 找到第一个非 0 时，和 left 指向的 第一个 0 进行交换，之后让 left++ 指向下一个元素。

此方法的巧妙在于：

• 慢指针 left 只有在交换后才向右移动。所以 left 的左侧，全部是已经处理好的数据，其中必然不包含 0 。

• 快指针 right 只有在指向非 0 时才交换，即遇到 0 就直接 right++ 跳过不进行操作。所以 left 和 right 之间，全部都是 0。

• 快指针 right 遇到 0 元素就跳过，当数组开头是连续非 0 元素时，left 和 right 会一起向右移动。

代码

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums.length == 1)
            return;
        int left = 0, right = 0;
        int len = nums.length;
        while (right < len) {
            if (nums[right] != 0) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
            }
            right++;
        }
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)