LeetCode hot 100 每日一题(4)--283. 移动零

开始进入双指针的学习部分。这是一道难度为简单的题目。
题目描述如下：

定一个数组 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

这道题目暂时没有说人话版本，因为读起来比较容易理解。

解法1

class Solution {public void moveZeroes(int[] nums) {// 首先判断传入的数组是否为空，如果为空直接返回，// 以防止后续操作出现空指针异常。if(nums == null){return;}// 定义指针 j，初始值为 0。j 用来记录数组中非零元素应放置的位置。int j = 0;// 第一个循环：遍历整个数组for(int i = 0; i < nums.length; i++){// 判断当前元素是否为非零if(nums[i] != 0){// 如果不是零，将该非零元素放到下标 j 的位置，// 这里相当于把所有非零元素往前填充，// j 表示当前应填充的位置。nums[j] = nums[i];// 填充完后，j 后移一位，为下一个非零元素留出位置。j++;}}// 第二个循环：将从下标 j 到数组末尾的所有位置都赋值为 0，// 因为前面的循环已经把所有非零元素按顺序存储在数组前面，// 剩下的位置应全部填充 0。for(int i = j; i < nums.length; i++){nums[i] = 0;}}
}

总结思路：

• 判断数组为空的情况：
  首先检查输入的 nums 是否为 null。如果为空，则没有操作的必要，直接返回。这是一种防御性编程的做法。

• 第一次遍历：提取非零元素

  • 使用变量 j 作为新数组中非零元素的位置指针。
  • 遍历整个数组，对于每个非零的元素，将它复制到下标为 j 的位置，然后 j 自增。
  • 这样遍历后，数组前 j 个位置存储了所有非零元素，而且它们的相对顺序没有改变。

• 第二次遍历：填充零值

  • 从下标 j 开始到数组末尾的部分，因为这些位置原本的值已经被非零元素覆盖，
  • 所以将它们全部置为 0，即实现将所有零移到数组的末尾。

实例

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

1. 初始状态：

   • 数组：[0, 1, 0, 3, 12]
   • 指针 j = 0

2. i = 0：

   • 当前元素：nums[0] = 0
   • 因为为 0，所以不做交换，j 保持不变。
   • 状态：[0, 1, 0, 3, 12]，j = 0

3. i = 1：

   • 当前元素：nums[1] = 1（非零）
   • 交换 nums[1] 与 nums[j]（即 nums[0]），交换 1 与 0。
   • 数组变为：[1, 0, 0, 3, 12]
   • 更新 j = 1
   • 状态：[1, 0, 0, 3, 12]，j = 1

4. i = 2：

   • 当前元素：nums[2] = 0
   • 为 0，不做操作。
   • 状态保持：[1, 0, 0, 3, 12]，j = 1

5. i = 3：

   • 当前元素：nums[3] = 3（非零）
   • 交换 nums[3] 与 nums[j]（即 nums[1]），交换 3 与 0。
   • 数组变为：[1, 3, 0, 0, 12]
   • 更新 j = 2
   • 状态：[1, 3, 0, 0, 12]，j = 2

6. i = 4：

   • 当前元素：nums[4] = 12（非零）
   • 交换 nums[4] 与 nums[j]（即 nums[2]），交换 12 与 0。
   • 数组变为：[1, 3, 12, 0, 0]
   • 更新 j = 3
   • 状态：[1, 3, 12, 0, 0]，j = 3

最终输出： [1, 3, 12, 0, 0]

问题与解答

[NOTE] 问题1
for(int i = j; i < nums.length; i++)这一段有一点不明白，为什么已经将非0元素移动到j左侧了，从j开始的当前位置仍然需要赋值为0，因为指针并没有改变数组的值吗？

• 解答：
  在第一个循环中，我们只是把所有非零元素复制到了数组前面（从下标 0 到 j-1 的位置），而并没有刻意清理原数组中 j 后面的元素。这部分位置可能保留着旧的值或未被覆盖的值，所以需要在第二个循环中将下标从 j 到数组末尾的元素全部设置为 0，以确保结果中零出现在所有非零元素之后。
  举个例子来看：[0, 1, 0, 3, 12]

1. 第一个循环复制非零元素，可能会得到这样的中间状态：

   • 当 i=1 处理非零元素 1 时，将其复制到下标 0，此时数组变为 [1, 1, 0, 3, 12]，j 变为 1；
   • 当 i=3 处理非零元素 3 时，将其复制到下标 1，此时数组变为 [1, 3, 0, 3, 12]，j 变为 2；
   • 当 i=4 处理非零元素 12 时，将其复制到下标 2，此时数组变为 [1, 3, 12, 3, 12]，j 变为 3。

2. 注意，此时 j=3 意味着前 3 个位置已存储正确的非零值，但数组后面的部分（下标 3 和 4）仍然保留了原来的值（分别是 3 和 12）。这显然不符合题目的要求。

3. 所以第二个循环从 j 开始，将下标 3 和 4 的元素赋值为 0，最终数组变成 [1, 3, 12, 0, 0]。

总结来说，第二个循环是用来“清空”数组中剩余的部分，确保非零元素右侧全部是 0。这一步是必要的，因为第一个循环只负责把非零元素复制到前面，而没有重置后面的位置。

[NOTE] 问题2：
题目中要求“请注意 ，必须在不复制数组的情况下原地对数组进行操作。”，采用指针可以原地对数组进行操作吗？

• 解答：
  在 Java 中，我们不会像 C/C++ 那样直接操作内存地址，但可以使用下标（index）来模拟指针的效果，从而实现原地修改数组。下面详细解释这点：

1. 原地操作：
   题目要求不复制数组、在原数组上直接进行修改。Java 中数组是引用类型，当我们将数组作为参数传递给函数时，实际上传递的是数组的引用。因此，对数组内容的修改会直接反映到原数组上，这就保证了“原地操作”。

2. 指针的概念：

   • 在 Java 中：
     Java 没有提供显式的指针（即可以直接访问和操作内存地址的功能），但我们可以使用变量（如整型下标或对象引用）来记录数组或集合中的位置。
     • 常见用法：
       在算法中，我们常使用两个或多个下标变量来代表不同的位置，从而实现类似“指针”的效果。例如，前面代码中的 j 就相当于一个指针，用于标记下一个应该存放非零元素的位置，而 i 用于遍历整个数组。这种方式虽然不是操作内存地址，但逻辑上达到了指针操作的目的。

因此，虽然 Java 中没有 C/C++ 风格的指针，但通过下标操作和数组引用，我们依然可以实现原地操作数组的目标。

总结

在这道题中，指针 其实指的是用下标变量来记录和操作数组中元素的位置，其用法总结如下：

• 模拟指针：
  Java 中没有直接操作内存地址的指针，但可以使用下标变量（如 i、j）来模拟指针的作用，通过记录当前位置，实现对数组的遍历和修改。

• 原地操作：
  由于 Java 中数组是引用类型，在方法内部对数组的修改会直接反映在原数组上，因此利用下标操作可以实现不复制数组的原地修改。

• 具体用法：
  在题目中，使用两个下标变量：

  • 一个下标（如 i）用来遍历数组中的每个元素。
  • 另一个下标（如 j）用来记录下一个非零元素应该放置的位置。

  第一轮遍历过程中，将所有非零元素依次复制到下标 j 指向的位置，然后 j 后移。第二轮遍历则从 j 到数组末尾，将这些位置填充为 0，从而将所有零移动到数组后面。

这种方法利用下标变量实现了类似指针的功能，既保证了原地修改的要求，又能保持非零元素的相对顺序。