欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2022年11月04日 08:44:19   作者:字節(jié)逆旅  
這篇文章主要為大家介紹了JavaScript?算法?復(fù)寫0雙指針解法,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

題目描述

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

注意:請不要在超過該數(shù)組長度的位置寫入元素。請對輸入的數(shù)組 就地 進行上述修改,不要從函數(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ī)律,如果實在不行,可以舉例推演:

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

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

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

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

/**
 * @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到頂點時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--;
    }
};

復(fù)雜度

時間復(fù)雜度:O(n)

空間復(fù)雜度:O(1)

以上就是JavaScript 算法 復(fù)寫0雙指針解法的詳細內(nèi)容,更多關(guān)于JavaScript 復(fù)寫0雙指針解法的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

最新評論