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 中更高效地處理數組操作，尤其是在性能敏感的場景中。
