題目介紹

鏈接: 1089. 復寫零

思路分析

那么這道題我們依然可以使用雙指針算法來解決

異地復寫

先不考慮題目的要求，直接就地在原數組上修改，可能不太好想，我們這里可以先在一個新開的數組上進行復寫

起始雙指針分別指向兩個數組0下標
如果cur指向的元素是非0，dest只把cur的值拷貝下來，無需復寫（只有0才復寫），然后兩者都++

cur如果指向0，那dest要拷貝兩次（復寫一次），然后兩者都++

后續也是如此




其實很簡單，就是模擬題目要求的復寫操作，非0不動，0復寫
對比一下題目的例子，結果是正確的

優化為就地復寫

那接下來我們就要嘗試在上面的基礎上進行優化，優化為原地復寫
怎么做呢？現在就只能在原數組上就地操作了

我們來嘗試一下：

上來cur指向非0
無需任何操作，兩者++即可，剛才我們要拷貝是因為dest指向一個新數組，現在都指向原數組

然后cur是0，所以要復寫一次0

那就變成這樣了。
這樣其實已經不行了，因為2被復寫的0覆蓋掉了，而cur++之后又指向了剛剛復寫的0，這樣后面都是0了，肯定的不對的

所以這道題從前向后移動指針是不行的，那我們可以反過來看看！

從后向前呢？

那兩個指針都指向最后一個元素嗎？
🆗，dest呢從最后一個位置開始，而cur，我們讓它一開始指向最后一個被處理的數。
因為最后一個被處理的數處理完畢一定是在數組最后一個位置的。
怎么找最后一個處理的數我們后面說，但是對于當前這個例子，我們知道最后一個處理的數，就是4

然后，就讓它們從后往前移動，進行像上面異地復寫一樣的操作就行了

答案正確！

總結一下：

先找到最后一個被處理的數，然后從后往前進行復寫即可

那現在關鍵問題在于，對于任意一個數組，我們如何找到它最后一個處理的元素是誰？

那么這個問題也可以使用雙指針來解決！
怎么做呢？
依然用上面這個例子

讓cur從0開始，dest從-1開始，然后，其實就是去模擬整個復寫的過程。
如果cur指向的是非0，讓dest走一步（只拷貝，不復寫），然后cur++；
如果是0，則dest走兩步（拷貝+復寫），然后cur++
當dest走到最后一個位置時候，就結束了，再走就越界了，此時，cur指向的元素就是最后一個被處理的數。
這個我就不再畫圖了，大家如果不理解可以自己畫一下圖走一遍。

但是，還有一種情況需要考慮：

如果最后一個被處理的數是0，這時dest往后走兩步有可能出現越界的情況。
所以，針對這種情況，我們可以處理一下：
此時0就是最后一個被處理的數，cur從0開始倒著處理，那此時dest應該拷貝+復寫，然后兩者都- -
但是此時dest是越界的，即執行拷貝的位置是越界的，所以cur直接- -，然后復寫一個0，然后兩者都- -。
即把n-1下標置0，cur- -，dest-=2。
后續正常處理就行。

AC代碼

上面分析的比較清楚了，代碼就不過多解釋了

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();// 1.先找到最后一個被處理的元素int cur = 0;int dest = -1;while (dest < n - 1) {if (arr[cur] != 0)dest++;elsedest += 2;if (dest >= n - 1)break; // 如果dest>=n-1（走到最后一個位置或者越界的情況），// 此時cur就是最后一個被處理的元素，不能再++了，直接breakcur++;}// 2.處理一下dest越界的情況if (dest == n) {arr[n - 1] = 0;cur--;dest -= 2;}// 3.從后往前進行復寫while (dest >= 0) {if (arr[cur] != 0)arr[dest] = arr[cur];else {arr[dest] = 0;arr[--dest] = 0;}cur--;dest--;}}
};