首頁猿問一個數(shù)組篩選的問題

一個數(shù)組篩選的問題

JavaScript

犯罪嫌疑人X 2019-05-25 15:46:39

vararr=["root/1",//處于同一分支"root/1/1/4/5","root/2/4/5",//不處于同一分支"root/2/4/3","root/3/3/3",//處于同一分支"root/3/3/3/5""root/5/6/7/8/9"http://沒有同一分支的節(jié)點]數(shù)組的每一項都是地址，代表此項所在的位置，可以想象成一棵節(jié)點數(shù)樹，root是根節(jié)點；比如"root/1/1/4/5"代表root下的1節(jié)點下的1節(jié)點下的4節(jié)點下的5節(jié)點然而我想達(dá)這樣一個目的：當(dāng)數(shù)組中出現(xiàn)了處在同一分支上的節(jié)點時，我只保留最頂部的節(jié)點所以我要達(dá)到篩選后：arr=["root/1","root/2/4/5","root/2/4/3","root/3/3/3","root/5/6/7/8/9"]怎么樣寫出這樣的篩選的方法，并且要求效率高，因為原數(shù)組的數(shù)據(jù)量很大，求大神賜教?。?

查看完整描述

2 回答

慕娘9325324

TA貢獻(xiàn)1783條經(jīng)驗獲得超4個贊

方法1functionstartsWith(s,p){leti=0while(p[i]&&s[i]===p[i])++ireturnp[i]===undefined&&(s[i]===undefined||s[i]==='/')}functionfilter(array){returnarray.sort().reduce((accum,path)=>{if(!accum.last)accum={store:[path],last:path}elseif(!startsWith(path,accum.last)){accum.store.push(path)accum.last=path}returnaccum},{store:[]}).store}思路：排序，排序后在同一根下的路徑會聚集在一起，且根在前面從前往后掃面數(shù)組，用一個變量accum.last記錄當(dāng)前的根。若遇到一個路徑其根不是當(dāng)前根，則說明這是一個新的根，將其加入結(jié)果數(shù)組中當(dāng)path很長時，path.indexOf效率不是太好，不考慮兼容問題的話可以使用path.startsWith(accum.last)。方法2functionfilter2(array){functiontraverse(node,current){if(node.end){results.push(current.join('/'))return}for(letpartofObject.keys(node.children))traverse(node.children[part],current.concat([part]))}lettree={children:{},end:false}letresults=[]array.forEach(path=>{letp=treefor(letpartofpath.split('/')){if(p.end)breakif(!p.children[part])p.children[part]={children:{},end:false}p=p.children[part]}p.end=true})traverse(tree,[])returnresults}思路：將各個路徑拆開，重新構(gòu)建成樹。再對樹進(jìn)行遍歷，找到各個根比較：方法1使用了排序，時間復(fù)雜度為$O(n\logn)$，空間復(fù)雜度為$O(1)$方法2的時間復(fù)雜度與數(shù)據(jù)具體的“多樣性程度”有關(guān)，當(dāng)路徑不長時可以接近$O(n)$；在極壞時需轉(zhuǎn)存出所有的數(shù)據(jù)，空間復(fù)雜度為$O(n)$$$$$

反對回復(fù) 2019-05-25

臨摹微笑

TA貢獻(xiàn)1982條經(jīng)驗獲得超2個贊

如果你能保證數(shù)組是有序的話，可以簡單的使用函數(shù)式編程的思維，遞歸：functionhead(arr){returnarr.slice(0,1);}functiontail(arr){returnarr.slice(1);}functionfilter(arr){if(arr.length===1)returnarr;returnhead(arr).concat(filter(tail(arr).filter(item=>item.indexOf(head(arr))===-1)))}vararr=["root/1",//處于同一分支"root/1/1/4/5","root/2/4/5",//不處于同一分支"root/2/4/3","root/3/3/3",//處于同一分支"root/3/3/3/5","root/5/6/7/8/9"http://沒有同一分支的節(jié)點];console.log(filter(arr));但是數(shù)據(jù)量大的話，就需要尾遞歸了，不然會棧溢出，你自己想想吧。另外，如果是無序的話，就需要稍微進(jìn)行改動。主要思路給你了，剩下的靠你自己了