一个数组筛选的问题

Question

var arr = [

    "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

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