283. 移动零

提示

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

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

示例 1:

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

示例 2:

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

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

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

我的想法：

不能复制数组，又用哈希吧？或者用一个判断？我不知道啊，快慢指针？根本不知道从哪里写比较合适。

1 分析题目

这道题要求我们原地（in-place）将数组中的所有 0 移动到末尾，同时保持非零元素的相对顺序。关键点有：

原地操作 - 不能创建新数组，必须直接修改原数组
保持非零元素顺序 - 非零元素的相对位置不能改变
最小化操作次数 - 这是进阶要求

你的思路分析

你的思考方向是正确的！提到了哈希表、判断条件和快慢指针，这些都是解决数组问题的常用思路：

哈希表：在这个问题中不需要，因为我们不需要记录元素频率或快速查找
判断条件：是的，我们需要判断元素是否为 0
快慢指针：这是解决这个问题的最佳方法！

2 正确解法：快慢指针法

快慢指针法是解决这类 "原地移动元素" 问题的经典方法。具体步骤：

快指针遍历数组，寻找非零元素
慢指针记录当前非零元素应该存放的位置
当快指针找到非零元素时，将其值赋给慢指针位置，然后慢指针前进一位
最后，将慢指针之后的所有位置填充为 0

java

运行

class Solution {public void moveZeroes(int[] nums) {int slow = 0;// 第一次遍历，将所有非零元素移到前面for (int fast = 0; fast < nums.length; fast++) {if (nums[fast] != 0) {nums[slow] = nums[fast];slow++;}}// 第二次遍历，将slow之后的所有位置填充为0for (int i = slow; i < nums.length; i++) {nums[i] = 0;}}
}

优化版本：减少操作次数

上面的方法需要两次遍历数组，实际上我们可以通过一次遍历来完成：

优化版本（一次遍历）

java

运行

class Solution {public void moveZeroes(int[] nums) {int slow = 0;for (int fast = 0; fast < nums.length; fast++) {if (nums[fast] != 0) {// 交换非零元素到前面int temp = nums[slow];nums[slow] = nums[fast];nums[fast] = temp;slow++;}}}
}

3 复杂度分析

时间复杂度：O (n)，只需要遍历一次数组
空间复杂度：O (1)，只需要常数级额外空间

你的不足与改进建议

对快慢指针不够熟悉：这是解决原地数组问题的重要技巧，建议多练习类似题目（如移除元素、删除有序数组中的重复项等）
缺乏解题模板：对于数组问题，可以总结常见的解题思路：双指针（快慢指针、左右指针）、滑动窗口、排序等
动手实践不足：不要害怕开始写代码，先尝试实现一个基本解法，再考虑优化

4 练习建议

推荐练习以下 LeetCode 题目来巩固快慢指针技巧：

26. 删除有序数组中的重复项
27. 移除元素
80. 删除有序数组中的重复项 II

5 快慢指针和左右指针

官方给出的题解：

class Solution {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 ;}
}

在这个 Java 实现中，left 和 right 指针本质上是快慢指针，而非传统意义上的左右指针。这两种指针模式的核心区别如下：

1. 快慢指针（Slow-Fast Pointers）

同向移动：两个指针从同一侧（通常是左侧）开始，以不同速度遍历数组。
核心逻辑：
- 慢指针：负责维护符合条件的元素位置（例如，非零元素的插入位置）。
- 快指针：负责快速遍历数组，寻找目标元素（例如，非零元素）。
典型应用：
- 移除数组中的特定元素（如移除 0、重复项）。
- 判断链表是否有环（Floyd 判圈算法）。

你的代码属于快慢指针：

left 指针：只有当 right 找到非零元素时才移动，相当于 “慢指针”。
right 指针：每次循环都移动，相当于 “快指针”。
当 right 遇到非零元素时，通过交换将其移到 left 位置，然后 left 前进。

2. 左右指针（Left-Right Pointers）

相向移动：两个指针分别从数组的左右两端开始，向中间移动。
核心逻辑：
- 左指针：从左向右移动，寻找需要交换到右侧的元素。
- 右指针：从右向左移动，寻找需要交换到左侧的元素。
典型应用：
- 反转数组（如反转字符串）。
- 两数之和（有序数组）。
- 快速排序中的分区操作。

左右指针的示例代码（反转数组）：

java

运行

public void reverse(int[] nums) {int left = 0, right = nums.length - 1;while (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}
}

3. 两者对比总结

特征	快慢指针	左右指针
移动方向	同向（左→右）	相向（左←→右）
速度关系	快指针移动更快	指针交替移动或按需移动
核心目的	筛选 / 移动特定元素	反转、查找配对元素
典型场景	移除元素、链表操作	反转数组、两数之和

4. 你的代码分析

你的实现使用了快慢指针，因为：

left 和 right 都从左侧开始，同向移动。
right 指针快速遍历数组，left 指针仅在交换时前进。
通过交换非零元素到左侧，保持了非零元素的相对顺序。

如果使用左右指针（相向移动），则无法保证非零元素的顺序（例如，可能将右侧的非零元素交换到左侧，打乱原有顺序）。因此，本题必须使用快慢指针。

总结

快慢指针：同向移动，用于筛选 / 移动元素，保持顺序。
左右指针：相向移动，用于反转、配对或分区操作。
你的代码是快慢指针的正确应用，适合本题需求

6 先做一下复制到新数组的方法

题友的启发：

“没有这么复杂，大家先做一下复制到新数组的方法（遍历nums，所有非0数复制到新数组），然后再想一想，怎么优化到使用原数组做为新数组即可。”

明白了！我们可以先通过复制到新数组的方法直观地解决问题，再逐步优化到原地操作。以下是完整的思路和代码实现：

方法一：复制到新数组（直观但不符合题目要求）

步骤：

遍历原数组 nums，将所有非零元素按顺序放入新数组。
新数组剩余位置补 0。
将新数组复制回原数组（题目要求原地修改）。

代码：

java

运行

public void moveZeroes(int[] nums) {int n = nums.length;int[] temp = new int[n];int index = 0;// 复制非零元素到新数组for (int num : nums) {if (num != 0) {temp[index++] = num;}}// 剩余位置补0while (index < n) {temp[index++] = 0;}// 将新数组复制回原数组System.arraycopy(temp, 0, nums, 0, n);
}

复杂度：

时间：O (n)
空间：O (n)（不符合题目要求）

方法二：原地操作（快慢指针优化）

优化思路：
直接在原数组上操作，通过双指针将非零元素移到左侧，剩余位置补 0。

步骤：

慢指针 left：记录下一个非零元素应存放的位置。
快指针 right：遍历数组，找到非零元素时与 left 交换，并右移 left。
遍历结束后，left 之后的位置全部补 0。

代码：

java

运行

public void moveZeroes(int[] nums) {int left = 0;// 将非零元素移到左侧for (int right = 0; right < nums.length; right++) {if (nums[right] != 0) {nums[left] = nums[right];left++;}}// 剩余位置补0while (left < nums.length) {nums[left++] = 0;}
}

复杂度：

时间：O (n)
空间：O (1)（符合题目要求）

方法三：进一步优化（一次遍历 + 交换）

思路：
在方法二的基础上，通过交换操作避免第二次遍历补 0。

步骤：

双指针 left 和 right 从左侧开始。
当 right 遇到非零元素时，与 left 交换，并同时右移两指针。
交换后，left 左侧的元素均为非零，left 指向的位置为下一个可能需要交换的 0。

代码：

java

运行

public void moveZeroes(int[] nums) {int left = 0;for (int right = 0; right < nums.length; right++) {if (nums[right] != 0) {// 交换非零元素到左侧int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;}}
}

复杂度：

时间：O (n)（仅一次遍历）
空间：O (1)

对比与总结

方法	时间复杂度	空间复杂度	操作次数
复制到新数组	O(n)	O(n)	2n
原地操作（两次遍历）	O(n)	O(1)	2n
原地操作（一次遍历）	O(n)	O(1)	n

结论：
方法三最优，通过一次遍历和交换操作，直接将所有非零元素移到左侧，同时将 0 移到右侧，操作次数最少。

7 System.arraycopy是什么？

System.arraycopy 是 Java 中用于数组复制的一个高效方法，位于 java.lang.System 类中。它允许你将一个数组的部分或全部元素复制到另一个数组中，是 Java 标准库中性能最优的数组复制方式之一。

核心语法

java

运行

public static void arraycopy(Object src,      // 源数组int srcPos,      // 源数组的起始位置Object dest,     // 目标数组int destPos,     // 目标数组的起始位置int length       // 需要复制的元素个数
)

关键特性

高效性：基于 JVM 底层实现，通常比手动循环复制快得多。
灵活性：支持部分复制（指定起始位置和长度）。
兼容性：
- 仅适用于相同类型的数组（基本类型或引用类型）。
- 对于引用类型，复制的是对象引用而非对象本身（浅拷贝）。
异常处理：
- 如果参数不合法（如数组类型不匹配、越界等），会抛出 ArrayStoreException 或 IndexOutOfBoundsException。

示例代码

1. 基本类型数组复制

java

运行

int[] src = {1, 2, 3, 4, 5};
int[] dest = new int[5];// 将 src 中索引 1 开始的 3 个元素复制到 dest 的索引 2 位置
System.arraycopy(src, 1, dest, 2, 3);// 输出 dest: [0, 0, 2, 3, 4]

2. 对象数组复制（浅拷贝）

java

运行

class Person {public int age;public Person(int age) { this.age = age; }
}Person[] src = {new Person(20), new Person(30)};
Person[] dest = new Person[2];System.arraycopy(src, 0, dest, 0, 2);// 修改 dest[0] 的属性会影响 src[0]
dest[0].age = 25;
System.out.println(src[0].age); // 输出: 25

与其他复制方式的对比

方法	适用场景	性能	特点
`System.arraycopy`	同类型数组高效复制	最优	底层实现，支持部分复制
`Arrays.copyOf`	创建新数组并复制全部元素	中等	封装了 `arraycopy`
`Arrays.copyOfRange`	创建新数组并复制部分元素	中等	封装了 `arraycopy`
`for` 循环	自定义复杂复制逻辑	最差	灵活但效率低
`clone()`	对象数组的浅拷贝	中等	仅适用于实现 Cloneable 的类

注意事项

避免数组重叠：如果源数组和目标数组是同一数组，且复制区域有重叠，可能导致意外结果。例如：

java

运行

int[] arr = {1, 2, 3, 4, 5};
// 错误示例：重叠复制可能导致数据覆盖
System.arraycopy(arr, 0, arr, 2, 3); // 结果可能不符合预期

多维数组：对于多维数组，arraycopy 只复制顶层数组的引用，不会递归复制子数组（仍为浅拷贝）。

常见应用场景

数组扩容：创建更大的新数组并复制原内容。
批量数据处理：高效转移数组中的部分数据。
集合实现：Java 中的 ArrayList 等集合类内部使用 arraycopy 实现动态扩容。

掌握 System.arraycopy 可以帮助你在 Java 中更高效地处理数组操作，尤其是在性能敏感的场景中。

我的想法：

1 分析题目

你的思路分析

2 正确解法：快慢指针法

优化版本：减少操作次数

优化版本（一次遍历）

3 复杂度分析

你的不足与改进建议

4 练习建议

5 快慢指针和左右指针

1. 快慢指针（Slow-Fast Pointers）

2. 左右指针（Left-Right Pointers）

3. 两者对比总结

4. 你的代码分析

总结

6 先做一下复制到新数组的方法

题友的启发：

方法一：复制到新数组（直观但不符合题目要求）

方法二：原地操作（快慢指针优化）

方法三：进一步优化（一次遍历 + 交换）

对比与总结

7 System.arraycopy是什么？

核心语法

关键特性

示例代码

1. 基本类型数组复制

2. 对象数组复制（浅拷贝）

与其他复制方式的对比

注意事项

常见应用场景

相关文章