首頁(yè) 猿問(wèn) 一道算法，沒(méi)想明白，幫忙看下

一道算法，沒(méi)想明白，幫忙看下

JavaScript

冉冉說(shuō) 2019-05-23 17:18:34

一個(gè)不定長(zhǎng)數(shù)組下標(biāo)0值為1下標(biāo)2和3值為null，下標(biāo)4值為5現(xiàn)在需要將null值替換最近的不為null的值比如{1,2,null,null,5,6,null};替換為{1,2,2,5,5,6,6};我使用的最暴力的遍歷循環(huán)做的，但這樣不是最優(yōu)的看上去應(yīng)該是用二分查找來(lái)，但沒(méi)想明白改怎么來(lái)？幫忙指點(diǎn)下

查看完整描述

2 回答

開滿天機(jī)

TA貢獻(xiàn)1786條經(jīng)驗(yàn) 獲得超13個(gè)贊

publicclassLatestInteger{publicstaticvoidmain(String[]args){Integer[]source={1,2,null,null,5,6,null};Integer[]left=newInteger[source.length];Integer[]right=newInteger[source.length];processLeft(source,left);processRight(source,right);Arrays.stream(left).forEach(item->System.out.print(item+""));System.out.println("-------------------");Arrays.stream(right).forEach(item->System.out.print(item+""));//System.exit(0);for(inti=0;iif(source[i]==null){intleftDistance=(left[i]==-1?Integer.MAX_VALUE:(i-left[i]));intrightDistance=(right[i]==-1?Integer.MAX_VALUE:(right[i]-i));source[i]=(leftDistance}}System.out.println("-------------------");Arrays.stream(source).forEach(item->System.out.print(item+""));}privatestaticvoidprocessLeft(Integer[]source,Integer[]left){left[0]=(source[0]==null?-1:0);for(inti=1;ileft[i]=(source[i]==null?left[i-1]:i);}}privatestaticvoidprocessRight(Integer[]source,Integer[]right){intstart=source.length-1;right[start]=(source[start]==null?-1:0);for(inti=start-1;i>=0;i--){right[i]=(source[i]==null?right[i+1]:i);}}}

反對(duì) 回復(fù) 2019-05-23

不負(fù)相思意

TA貢獻(xiàn)1777條經(jīng)驗(yàn) 獲得超10個(gè)贊

艸，看錯(cuò)了，看成了{(lán)1,2,2,2,5,6,6}了。。。如果照題主的意思，是生成快照同步替換，那null中間的null確實(shí)處理不了從題主的示例{1,2,null,null,5,6,null}轉(zhuǎn)化為{1,2,2,5,5,6,6}可以看出來(lái)：替換的順序是從左往右替換時(shí)優(yōu)先使用左邊的值那么可以推斷出：如果某個(gè)null左邊沒(méi)有實(shí)數(shù)的話，應(yīng)當(dāng)是使用右邊的值那么如果右邊第一位沒(méi)有，應(yīng)該循序找下一位