JavaScript?算法實現(xiàn)復(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)文章
js檢測標(biāo)題與描述中的關(guān)鍵詞發(fā)現(xiàn)就替換或跳轉(zhuǎn)到別的頁面
這篇文章主要介紹了js檢測標(biāo)題與描述中的關(guān)鍵詞發(fā)現(xiàn)就替換或跳轉(zhuǎn)到別的頁面的實現(xiàn)方法,主要是分享它的編程思路與加密方法2021-06-06原生js操作checkbox用document.getElementById實現(xiàn)
js操作checkbox本人建議用document.getElementById(checkbox_id).checked不推薦使用jquery操作checkbox,感興趣的朋友不要錯過2013-10-10JavaScript 操作鍵盤的Enter事件(鍵盤任何事件),兼容多瀏覽器
JavaScript 操作鍵盤的Enter事件(鍵盤任何事件),支持各種瀏覽器,需要的朋友可以參考下。2010-10-10js單頁hash路由原理與應(yīng)用實戰(zhàn)詳解
本篇文章主要介紹了js單頁hash路由原理與應(yīng)用實戰(zhàn)詳解,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-08-08JavaScript防抖與節(jié)流的實現(xiàn)與注意事項
防抖和節(jié)流嚴(yán)格算起來應(yīng)該屬于性能優(yōu)化的知識,但實際上遇到的頻率相當(dāng)高,處理不當(dāng)或者放任不管就容易引起瀏覽器卡死,下面這篇文章主要給大家介紹了關(guān)于JavaScript防抖與節(jié)流的實現(xiàn)與注意事項,需要的朋友可以參考下2022-03-03javascript?Echart可視化學(xué)習(xí)
這篇文章主要為大家介紹了Echart可視化學(xué)習(xí)的方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助2022-01-01