JavaScript?算法實(shí)現(xiàn)復(fù)寫0雙指針解法

更新時間：2022年11月04日 08:44:19 作者：字節(jié)逆旅

這篇文章主要為大家介紹了JavaScript?算法?復(fù)寫0雙指針解法，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

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

注意：請不要在超過該數(shù)組長度的位置寫入元素。請對輸入的數(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]

提示：

1 <= arr.length <= 104

0 <= arr[i] <= 9

題解

題目表示把原數(shù)組中的零都復(fù)寫一遍，看示例應(yīng)該能明白什么意思，就是單純地把原數(shù)組中為0的元素重復(fù)寫一遍，復(fù)寫的元素要把原索引位后面的元素往后擠一個位置出來，這樣原數(shù)組中每出現(xiàn)一個0，新數(shù)組就將從原數(shù)組中擠掉一個末位的元素。

對比新舊兩個數(shù)組，會發(fā)現(xiàn)新數(shù)組中的所有元素都來自舊數(shù)組，而新數(shù)組中只用到舊數(shù)組中左側(cè)的一部分元素，如果用i來表示舊數(shù)組的索引，在遍歷結(jié)束后新數(shù)組中用到的舊數(shù)組中的索引位應(yīng)該是0-i，且i<arr.length。也就是新數(shù)組中的指針增加到arr.length - 1時，舊數(shù)組的指針停留在i，這時就出現(xiàn)了快慢指針的場景了。

前面定義了慢指針i，用來標(biāo)記舊數(shù)組；再定義一個快指針j，用來標(biāo)記新數(shù)組。

分幾步走：

計算出快慢指針
推算快慢指針規(guī)律
從后往前覆寫舊數(shù)組

這里主要講下規(guī)律，如果實(shí)在不行，可以舉例推演：

例1：

[0,1,2] >> i= 1

[0,0,1] >> j=2

例2：

[1,0,2,0,3] >> i = 3

[1,0,0,2,0] >> j = 4

例3：

[1,0,2,3,4] >> i = 3

[1,0,0,2,3] >> j = 4

基本上我可以靠人肉智能直接寫出來，從左往右，非零直接寫，遇到0寫兩遍，直到棧頂。例2和例3的快慢指針是一樣的，他們區(qū)別的點(diǎn)是最后一個元素，一個是0一個不是0。如果定義一個變量，按照前面人肉智能的邏輯，用來表示舊數(shù)組的元素要在新數(shù)據(jù)寫的次數(shù)之和t，這個區(qū)別就出來了：第一個是3，第二個是6(后面的一個0沒位置了)，第三個是5。最后一個數(shù)要么是0，要么不是0，如果是0，t肯定比arr.length大1。

其實(shí)快指針的值j是固定的就是arr.length - 1，按這思路可以求出慢指針：

    const n = arr.length;
    let top = 0; // 新數(shù)組不計溢出時需要添加的個數(shù)
    let i = -1; // 舊數(shù)組的索引位，top到頂點(diǎn)時i停止
    while (top < n) {
        i++;
        if (arr[i] !== 0) {
            top++;
        } else {
            top += 2;
        }
    }

算出慢指針i的值，新數(shù)組中的元素就定好了，接下來就是把值塞進(jìn)去，因?yàn)轭}目要求不能定義新數(shù)組，要塞進(jìn)去就只能從后面塞。具體代碼如下：

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function(arr) {
    const n = arr.length;
    let top = 0; // 新數(shù)組的極限索引
    let i = -1; // 舊數(shù)組的索引位，top到頂點(diǎn)時i停止
    while (top < n) {
        i++;
        if (arr[i] !== 0) {
            top++;
        } else {
            top += 2;
        }
    }
    let j = n - 1;
    if (top === n + 1) { 
        // 超出原數(shù)組兩個索引位，說明最后一位是0
        arr[j] = 0;
        j--;
        i--;
    } 
    // i是原數(shù)組索引位，新數(shù)組只用到0-i的元素
    while (j >= 0) {
        arr[j] = arr[i];
        j--;
        // 如果當(dāng)前i索引位是0，則新數(shù)組還要向后退一位且用0賦值
        if (arr[i] === 0) {
            arr[j] = arr[i];
            j--;
        } 
        i--;
    }
};