JavaScript?算法實(shí)現(xiàn)復(fù)寫0雙指針解法
題目描述
給你一個(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--; } };
復(fù)雜度
時(shí)間復(fù)雜度:O(n)
空間復(fù)雜度:O(1)
以上就是JavaScript 算法 復(fù)寫0雙指針解法的詳細(xì)內(nèi)容,更多關(guān)于JavaScript 復(fù)寫0雙指針解法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
js檢測(cè)標(biāo)題與描述中的關(guān)鍵詞發(fā)現(xiàn)就替換或跳轉(zhuǎn)到別的頁(yè)面
這篇文章主要介紹了js檢測(cè)標(biāo)題與描述中的關(guān)鍵詞發(fā)現(xiàn)就替換或跳轉(zhuǎn)到別的頁(yè)面的實(shí)現(xiàn)方法,主要是分享它的編程思路與加密方法2021-06-06原生js操作checkbox用document.getElementById實(shí)現(xiàn)
js操作checkbox本人建議用document.getElementById(checkbox_id).checked不推薦使用jquery操作checkbox,感興趣的朋友不要錯(cuò)過(guò)2013-10-10JavaScript 操作鍵盤的Enter事件(鍵盤任何事件),兼容多瀏覽器
JavaScript 操作鍵盤的Enter事件(鍵盤任何事件),支持各種瀏覽器,需要的朋友可以參考下。2010-10-10js單頁(yè)hash路由原理與應(yīng)用實(shí)戰(zhàn)詳解
本篇文章主要介紹了js單頁(yè)hash路由原理與應(yīng)用實(shí)戰(zhàn)詳解,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-08-08JavaScript防抖與節(jié)流的實(shí)現(xiàn)與注意事項(xiàng)
防抖和節(jié)流嚴(yán)格算起來(lái)應(yīng)該屬于性能優(yōu)化的知識(shí),但實(shí)際上遇到的頻率相當(dāng)高,處理不當(dāng)或者放任不管就容易引起瀏覽器卡死,下面這篇文章主要給大家介紹了關(guān)于JavaScript防抖與節(jié)流的實(shí)現(xiàn)與注意事項(xiàng),需要的朋友可以參考下2022-03-03js數(shù)字計(jì)算 誤差問(wèn)題的快速解決方法
下面小編就為大家?guī)?lái)一篇js數(shù)字計(jì)算 誤差問(wèn)題的快速解決方法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-02-02json屬性名為什么要雙引號(hào)(個(gè)人猜測(cè))
json屬性名為什么要雙引號(hào)?更加規(guī)范,利于解析、避免class等關(guān)鍵字引起的不兼容問(wèn)題,需要的朋友可以參考下2014-07-07javascript?Echart可視化學(xué)習(xí)
這篇文章主要為大家介紹了Echart可視化學(xué)習(xí)的方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助2022-01-01