LC283. 移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。 示例 1: 输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2: 输入: nums = [0] 输出: [0] 提示: 1 <= nums.length <= 10^4 -2^31 <= nums[i] <= 2^31 - 1 进阶：你能尽量减少完成的操作次数吗？

题目解析

题目在说什么

给你一个数组，里面有一些数字，其中可能有0。你的任务是把所有的0都挪到数组的末尾，而且不能改变其他非0数字的顺序。比如 [0,1,0,3,12] 变成 [1,3,12,0,0]。注意：不能复制一个新数组，只能在原来的数组上动手脚（原地操作）。

思路是怎么来的

想象一下你在整理一个书架，书架上有些书是“空位”（代表0），有些是真正的书（代表非0数字）。你想把所有的空位都推到最右边，而书按照原来的顺序排在左边。

如果你一本一本看过去，看到书就把它放到左边第一个空位上，然后继续看下一本。这样，所有书都会被“挤”到左边，而空位自然就跑到右边了。

这就是我们算法的核心思想：用一个“慢指针”标记左边第一个空位的位置，用一个“快指针”从头到尾扫描每一本书。遇到书（非0数字），就把它放到慢指针指向的空位，然后慢指针往后移一位（因为那个空位被填满了，下一个空位在右边）。遇到空位（0），就跳过，继续看下一个。

这样扫描完一遍后，所有非0数字都按顺序排在了左边，慢指针指向的位置就是第一个空位（0）应该开始的位置。最后，把慢指针之后的所有位置都变成0就行了。

代码逐步拆解

我们来看参考代码，一行一行解释。

int slow = 0;

• slow 是慢指针，它指向“下一个非0数字应该放的位置”。一开始，我们假设第一个位置（索引0）可能是空位，所以 slow = 0。

for (int fast = 0; fast < nums.length; fast++) {

• fast 是快指针，它从数组的第一个位置（索引0）开始，一直走到最后一个位置。fast 负责检查每个位置上的数字。

    if (nums[fast] != 0) {

• 如果 fast 指向的数字不是0，说明这是一本“书”，需要把它放到左边去。

        nums[slow] = nums[fast];

• 把这本书（nums[fast]）放到 slow 指向的位置。注意：这个位置原来可能已经有数字了（可能是0，也可能是之前放过来的书），没关系，我们直接覆盖。因为 slow 指向的是“第一个空位”，所以覆盖掉的是空位或者已经被处理过的位置，不会丢失有用的信息。

        slow++;

• 放好书之后，slow 要往后移一位，因为当前这个位置已经放好了书，下一个空位在右边。

    }
}

• 如果 nums[fast] == 0，就什么都不做，直接看下一个 fast。因为0是空位，不需要移动，它最终会被“挤”到右边。