目錄

1. 移動零

1.1?思路解析

1.2?代碼實現

2. 復寫零

2.1 思路解析

2.2?代碼實現

---

1. 移動零

283. 移動零 - 力扣（LeetCode）

給定一個數組?nums，編寫一個函數將所有?0?移動到數組的末尾，同時保持非零元素的相對順序。

請注意?，必須在不復制數組的情況下原地對數組進行操作。

示例 1:

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

示例 2:

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

我們可以用雙指針來解決上方問題，這里的雙指針用數組下標代替與C++的指針作區分。此問題不涉及整個數組的平移。

1.1?思路解析

a）先定義兩個指針，dest 和 cur，我們可以讓 cur 來遍歷整個數組。

b）我們可以用雙指針來把整個數組分為三個區域：[0,dest] 非零區域、[dest+1,cur-1] 零區域、[cur,n-1] 待處理區域。上述問題我在之后將統一稱為數組劃分問題。

c）具體的思路是，讓 cur 從零開始，dest 從 -1位置開始。當 cur 遇到零元素時跳過 cur++，當 cur 遇到非零元素時 dest++ ，并且讓當前 cur 所指元素和 dest++ 后的所指元素交換位置。

1.2?代碼實現

class Solution {public void moveZeroes(int[] nums) {for(int cur = 0,dest = -1; cur<nums.length;cur++){if(nums[cur] != 0){int tmp = nums[cur];dest++;nums[cur] = nums[dest];nums[dest] = tmp;}}}
}

2. 復寫零

1089. 復寫零 - 力扣（LeetCode）

2.1 思路解析

a）我們可以定義雙指針來解決該問題，定義 cur 和 dest。

b）cur 遇到的情況分為兩種，遇到零 和 非零元素。

c）我們可以讓 cur 遇到非零元素時，dest 在當前位置復寫一個；同理 cur 遇到零元素時，dest 在當前位置和后一位復寫兩個零。

但是如果我們從左往右來進行操作，如果遇到 [1,0,2,1] 這種數組的話，操作結果就不符合題目要求，因為 dest 已經在 cur 前面了，會造成數據丟失。如下圖所示：

所以我們需要轉變思路：

a）先找到最后一個復寫的數

先定義兩個指針 cur 和 dest，讓 cur 的初始值為0，dest 初始值為 -1。讓 dest 走 cur 遍歷的數來判斷最后一個復寫的數。當 cur 遇到非零元素時，dest 移動一位，cur 遇到零元素時，dest 移動兩位。當 dest 遍歷完整個數組時，cur 所指的下標就是最后一個復寫的數。

b）處理邊界問題

當我們遇到類似 [2,0,3,5,0,4] 這樣的數組時就會發生 dest 所在的位置越界情況，從后向前的復寫操作就會報錯，解決方案就是 arr[dest-1] = 0; cur --;dest -= 2。越界情況如下圖所示：

c）從后向前完成復寫操作

當 cur 遇到非零元素時，把 cur 的元素覆蓋到 dest 所在的位置，arr[dest--] = arr[cur--]；當 cur 遇到零元素時，把零元素覆蓋到 dest 當前位置和前一位。

2.2?代碼實現

class Solution {public void duplicateZeros(int[] arr) {int cur = 0, dest = -1;while(cur<arr.length){if(arr[cur] == 0){dest += 2;}else{dest ++;}if(dest>=arr.length-1){break;}cur++; }if(dest == arr.length){arr[dest-1] = 0;dest -= 2;cur --;}while(cur>=0){if(arr[cur] == 0){arr[dest--] = 0;arr[dest--] = 0;cur--;}else{arr[dest--] = arr[cur--];}}}
}