目錄

題目描述

題目解析

算法原理講解

代碼

---

題目描述

1089. 復寫零

給你一個長度固定的整數數組?arr?，請你將該數組中出現的每個零都復寫一遍，并將其余的元素向右平移。

注意：請不要在超過該數組長度的位置寫入元素。請對輸入的數組?就地?進行上述修改，不要從函數返回任何東西。

示例 1：

輸入：arr = [1,0,2,3,0,4,5,0]
輸出：[1,0,0,2,3,0,0,4]
解釋：調用函數后，輸入的數組將被修改為：[1,0,0,2,3,0,0,4]

示例 2：

輸入：arr = [1,2,3]
輸出：[1,2,3]
解釋：調用函數后，輸入的數組將被修改為：[1,2,3]

提示：

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 9

題目解析

????????題目意思就是遇到0了再寫一遍0，其他元素向右平移就行。只能在原來數組上修改，也就是空間復雜度為0.

算法原理講解

????????一般像這種在數組中移動一些數的題目，也是用雙指針算法來解決這個問題。

????????雙指針算法是根據異地解法的操作，優化成雙指針的就地操作。

異地操作

異地操作就是，重新開辟一個數組。

????????定義兩個指針，cur用來掃描原數組，dest用來更新新數組。

????????當cur對應的值不等于0時，dest更新一個數，將cur值直接填入dest的位置，dest++，cur++就行。

????????當cur對應的值等于0時，dest指針更新兩個數，都填入0,cur++就行。

????????當dest=arrSize就結束了。

就地操作

????????就是不用重新開辟數組，也就是題目要求的那樣，我們可以把cur和dest這兩個指針，都放在原數組上。

? ? ? ?用雙指針解決復寫問題的步驟

1.找到最后一個復寫的數

2.從后向前完成復寫

????????讓cur指向最后一個復寫的數，對于[1,0,2,3,0,4,5,0]這個數組，最后一個復寫的數是4，所以讓cur指向4 ，best指向最后一個位置就行。

cur指向的這個數是非零的，所以復寫一次就行，復寫完后，cur--,dest--。

這次cur指向0，那就復寫兩次，后cur--。

從圖中可以看出，當cur和dest都指向-1的時候就復寫完成了。

接下來有一個問題就是？——怎么找到最后一個復寫的數

????????還是利用雙指針算法，定義兩個指針cur和dest,cur用來掃描數組，dest用來標識最后一個復寫的數。

cur指向的值決定dest向后移動兩步還是移動一步

1.先判斷cur里面的值

2.決定dest走兩步還是走一步

3.在判斷dest到沒到結尾

4.沒到結尾再cur++

????????咱們一步一步來，arr[cur]現在指向了1，所以dest走一步到達下標為0的位置，dest沒有走到結尾，所以cur++。

arr[cur]現在指向了0，所以dest走兩步到達下標為2的位置，dest沒有走到結尾所以cur++。

arr[cur]現在指向了2，所以dest走一步到達下標為3的位置，dest沒有走到結尾所以cur++。

arr[cur]現在指向了3，所以dest走一步到達下標為4的位置，dest沒有走到結尾所以cur++。

arr[cur]現在指向了0，所以dest走兩步到達下標為6的位置，dest沒有走到結尾所以cur++。

arr[cur]現在指向了4，所以dest走一步到達下標為7的位置，dest走到結尾返回cur。

????????對于這個數組這種方法是剛好的，那么如果是【1，0，2，3，0，4】

arr[cur]現在指向了1，所以dest走一步到達下標為0的位置，dest沒有走到結尾所以cur++。

arr[cur]現在指向了0，所以dest走兩步到達下標為2的位置，dest沒有走到結尾所以cur++。

arr[cur]現在指向了2，所以dest走一步到達下標為3的位置，dest沒有走到結尾所以cur++。

arr[cur]現在指向了3，所以dest走一步到達下標為4的位置，dest沒有走到結尾所以cur++。

?????????arr[cur]現在指向了0，所以dest走兩步到達下標為6的位置，但是這個數組沒有下標6最大直到5,所以會產生越界。

????????接下來，我們怎么解決這個問題，我們要明白越界是怎么產生的，是因為復寫0,復寫兩次就產生了越界。這個情況我們單獨處理一下。

那么怎么處理呢？我們在復寫的時候將最后一個位置，和越界的那個位置都復寫成0。但是越界那個位置不能修改成0，我們只需要把最后一個位置修改成0（直接在這里復寫），也就是arr[arrSzie-1]=0,就可以。

修改之后我們將dest向前移動兩步，cur向前移動一步

cur現在就是最后一個復寫的值，接下來復寫就從dest現在的位置開始復寫。

代碼

void duplicateZeros(int* arr, int arrSize) {//找到最后一個復寫的位置int cur=0;int dest=-1;while(cur<arrSize){if(arr[cur]==0)dest+=2;if(arr[cur]!=0)dest+=1;//如果dest到達最后一個位置就跳出循環//如果剛好的話是等于arrSzie-1，有越界的時候是等于arrSizeif(dest==arrSize-1||dest==arrSize)break;cur++;}//處理邊界if(dest==arrSize){arr[arrSize-1]=0;cur-=1;dest-=2;}while(cur>=0&&dest>=0){if(arr[cur]==0){arr[dest--]=arr[cur];arr[dest--]=arr[cur--];}else{arr[dest--]=arr[cur--];}}}