題目描述

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

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

示例 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的元素重復寫一遍，復寫的元素要把原索引位后面的元素往后擠一個位置出來，這樣原數組中每出現(xiàn)一個0，新數組就將從原數組中擠掉一個末位的元素。

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

前面定義了慢指針i，用來標記舊數組；再定義一個快指針j，用來標記新數組。

分幾步走：

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

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

例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ū)別的點是最后一個元素，一個是0一個不是0。如果定義一個變量，按照前面人肉智能的邏輯，用來表示舊數組的元素要在新數據寫的次數之和t，這個區(qū)別就出來了：第一個是3，第二個是6(后面的一個0沒位置了)，第三個是5。最后一個數要么是0，要么不是0，如果是0，t肯定比arr.length大1。

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

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

算出慢指針i的值，新數組中的元素就定好了，接下來就是把值塞進去，因為題目要求不能定義新數組，要塞進去就只能從后面塞。具體代碼如下：

/**
 * @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; // 新數組的極限索引
    let i = -1; // 舊數組的索引位，top到頂點時i停止
    while (top < n) {
        i++;
        if (arr[i] !== 0) {
            top++;
        } else {
            top += 2;
        }
    }
    let j = n - 1;
    if (top === n + 1) { 
        // 超出原數組兩個索引位，說明最后一位是0
        arr[j] = 0;
        j--;
        i--;
    } 
    // i是原數組索引位，新數組只用到0-i的元素
    while (j >= 0) {
        arr[j] = arr[i];
        j--;
        // 如果當前i索引位是0，則新數組還要向后退一位且用0賦值
        if (arr[i] === 0) {
            arr[j] = arr[i];
            j--;
        } 
        i--;
    }
};

復雜度

時間復雜度：O(n)

空間復雜度：O(1)

以上就是JavaScript 算法 復寫0雙指針解法的詳細內容，更多關于JavaScript 復寫0雙指針解法的資料請關注腳本之家其它相關文章！