給你一個(gè)長(zhǎng)度固定的整數(shù)數(shù)組 arr ，請(qǐng)你將該數(shù)組中出現(xiàn)的每個(gè)零都復(fù)寫一遍，并將其余的元素向右平移。

注意：請(qǐng)不要在超過該數(shù)組長(zhǎng)度的位置寫入元素。請(qǐng)對(duì)輸入的數(shù)組 就地 進(jìn)行上述修改，不要從函數(shù)返回任何東西。

示例 1：

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

示例 2：

輸入：arr = [1,2,3]
輸出：[1,2,3]
解釋：調(diào)用函數(shù)后，輸入的數(shù)組將被修改為：[1,2,3]

算法思路

本題使用雙指針?biāo)惴?

如果[從前往后]進(jìn)行原地復(fù)寫的話, 由于0會(huì)復(fù)寫兩次, 導(dǎo)致沒有被復(fù)寫的數(shù)被[覆蓋]掉了. 因此我們使用[從后向前]的復(fù)寫策略.

算法流程

1. 初始化兩個(gè)指針cur = 0, dest = -1

2. 先找到最后一個(gè)復(fù)寫的數(shù), 使cur指向最后一個(gè)復(fù)寫的數(shù), dest指向從后往前復(fù)寫的起始位置, 應(yīng)該是數(shù)組的最后一個(gè)元素的位置.

   • 當(dāng)cur < arr.length時(shí), 一直執(zhí)行下面的循環(huán):

     • 先判斷cur位置的值

       • 如果為0, dest向后移動(dòng)2步
       • 如果不是0, dest向后移動(dòng)1步

     • 判斷dest是否已經(jīng)到達(dá)數(shù)組的最后一個(gè)元素的位置, 如果到達(dá)了, 就終止循環(huán).

     • cur++, 繼續(xù)判斷

3. 處理邊界情況. 判斷dest是否發(fā)生越界(dest = arr.length):

   如果發(fā)生了越界:

   • 讓數(shù)組arr[arr.length - 1] = 0
   • cur--
   • dest -= 2

4. "從后向前"完成復(fù)寫操作, 只要cur >= 0

   • 判斷cur位置的值
     • 如果是0: dest和dest - 1位置的值改為0, dest -= 2
     • 如果不是0: dest位置的值改為cur位置的值, dest--
   • cur--

Java代碼

class Solution {public static 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[arr.length - 1] = 0;dest -= 2;cur--;}while (cur >= 0) {if(arr[cur] == 0) {arr[dest--] = 0;arr[dest--] = 0;cur--;} else {arr[dest--] = arr[cur--];}}}
}

時(shí)間復(fù)雜度: O(N) 空間復(fù)雜度O(1)