一个数组筛选的问题

Question

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"//没有同一分支的节点]数组的每一项都是地址，代表此项所在的位置，可以想象成一棵节点数树，root是根节点；比如"root/1/1/4/5"代表root下的1节点下的1节点下的4节点下的5节点然而我想达这样一个目的：当数组中出现了处在同一分支上的节点时，我只保留最顶部的节点所以我要达到筛选后：arr=["root/1","root/2/4/5","root/2/4/3","root/3/3/3","root/5/6/7/8/9"]怎么样写出这样的筛选的方法，并且要求效率高，因为原数组的数据量很大，求大神赐教！！

Answer 1

方法1
functionstartsWith(s,p){
leti=0
while(p[i]&&s[i]===p[i])++i
returnp[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
}
思路：
排序，排序后在同一根下的路径会聚集在一起，且根在前面
从前往后扫面数组，用一个变量accum.last记录当前的根。若遇到一个路径其根不是当前根，则说明这是一个新的根，将其加入结果数组中
当path很长时，path.indexOf效率不是太好，不考虑兼容问题的话可以使用path.startsWith(accum.last)。
方法2
functionfilter2(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=tree
for(letpartofpath.split('/')){
if(p.end)break
if(!p.children[part])p.children[part]={children:{},end:false}
p=p.children[part]
}
p.end=true
})
traverse(tree,[])
returnresults
}
思路：将各个路径拆开，重新构建成树。再对树进行遍历，找到各个根
比较：
方法1使用了排序，时间复杂度为$O(n\logn)$，空间复杂度为$O(1)$
方法2的时间复杂度与数据具体的“多样性程度”有关，当路径不长时可以接近$O(n)$；在极坏时需转存出所有的数据，空间复杂度为$O(n)$
$$$$
                            

Answer 2

如果你能保证数组是有序的话，可以简单的使用函数式编程的思维，递归：
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"//没有同一分支的节点
];
console.log(filter(arr));
但是数据量大的话，就需要尾递归了，不然会栈溢出，你自己想想吧。另外，如果是无序的话，就需要稍微进行改动。主要思路给你了，剩下的靠你自己了