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

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

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

題目描述

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

注意：請(qǐng)不要在超過(guò)該數(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]

提示：

1 <= arr.length <= 104

0 <= arr[i] <= 9

題解

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

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

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

分幾步走：

計(jì)算出快慢指針
推算快慢指針規(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

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

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

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

算出慢指針i的值，新數(shù)組中的元素就定好了，接下來(lái)就是把值塞進(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)時(shí)i停止
    while (top < n) {
        i++;
        if (arr[i] !== 0) {
            top++;
        } else {
            top += 2;
        }
    }
    let j = n - 1;
    if (top === n + 1) { 
        // 超出原數(shù)組兩個(gè)索引位，說(shuō)明最后一位是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--;
    }
};