Leetcode 08 java

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 移动到末尾，同时保持非零元素的相对顺序。关键点有：

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

你的思路分析

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

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

2 正确解法：快慢指针法

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

1. 快指针遍历数组，寻找非零元素
2. 慢指针记录当前非零元素应该存放的位置
3. 当快指针找到非零元素时，将其值赋给慢指针位置，然后慢指针前进一位
4. 最后，将慢指针之后的所有位置填充为 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)，只需要常数级额外空间

你的不足与改进建议

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

4 练习建议

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

1. 26. 删除有序数组中的重复项
2. 27. 移除元素
3. 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. 你的代码分析

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

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

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

总结

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

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

题友的启发：

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

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

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

步骤：

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

代码：

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。

步骤：

1. 慢指针 left：记录下一个非零元素应存放的位置。
2. 快指针 right：遍历数组，找到非零元素时与 left 交换，并右移 left。
3. 遍历结束后，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。

步骤：

1. 双指针 left 和 right 从左侧开始。
2. 当 right 遇到非零元素时，与 left 交换，并同时右移两指针。
3. 交换后，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       // 需要复制的元素个数
)

关键特性

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

注意事项

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

   java

   运行

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

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

常见应用场景

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

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