這是小川的第392次更新，第423篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級別的第255題（順位題號是1089）。給定一個固定長度的整數(shù)數(shù)組arr，復(fù)制每次出現(xiàn)的零，將剩余的元素向右移動。

請注意，不會寫入超出原始數(shù)組長度的元素。

對輸入數(shù)組進(jìn)行上述修改，不要從函數(shù)返回任何內(nèi)容。

例如：

輸入：[1,0,2,3,0,4,5,0]
輸出：null
說明：調(diào)用函數(shù)后，輸入數(shù)組被修改為：[1,0,0,2,3,0,0,4]

輸入：[1,2,3]
輸出：null
說明：調(diào)用函數(shù)后，輸入數(shù)組被修改為：[1,2,3]

注意：

• 1 <= arr.length <= 10000

• 0 <= arr [i] <= 9
  
  

02 第一種解法

新建一個List，遍歷arr中的元素，如果為0，添加兩次到List中，然后將List中的前n個元素回寫到arr中，n為arr的長度。

public void duplicateZeros(int[] arr) {
    List<Integer> list = new ArrayList<Integer>();
    for (int num : arr) {
        if (num == 0) {
            list.add(0);
        }
        list.add(num);
    }
    for (int i=0; i<arr.length; i++) {
        arr[i] = list.get(i);
    }
}

03 第二種解法

我們也可以不使用List，將arr復(fù)制一份出來，創(chuàng)建一個索引，遍歷復(fù)制數(shù)組，將元素回寫到arr中，遇到0就重復(fù)賦值一次。

public void duplicateZeros2(int[] arr) {
    int n = arr.length, index = 0;
    int[] copy = arr.clone();
    for (int num : copy) {
        if (index >= n) {
            break;
        }
        if (index+1 < n && num == 0) {
            arr[index++] = 0;
            arr[index++] = 0;
        } else {
            arr[index++] = num;
        }
    }
}

04 第三種解法

我們也可以不使用額外的空間，通過雙指針來實(shí)現(xiàn)。

先遍歷arr，統(tǒng)計(jì)其中元素值為0的元素個數(shù)，記為count，從后往前遍歷，一個長度為arr的長度，另外一個長度為arr的長度加count，遇到0就重復(fù)回寫一次。

public void duplicateZeros3(int[] arr) {
    int count = 0;
    for (int num : arr) {
        if (num == 0) {
            count++;
        }
    }
    int n = arr.length, n2 = n + count;
    // i是原數(shù)組的索引，j是原數(shù)組的長度加count
    for (int i=n-1, j= n2-1; i < j; i--, j--) {
        if (arr[i] != 0) {
            if (j < n) {
                arr[j] = arr[i];
            }
        } else {
            // 遇到0，再重復(fù)一次
            if (j < n) {
                arr[j] = arr[i];
            }
            j--;
            if (j < n) {
                arr[j] = arr[i];
            }
        }
    }
}

05 小結(jié)

算法專題目前已連續(xù)日更超過八個月，算法題文章261+篇，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對我最大的回報(bào)和支持！