一个数组筛选的问题

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

方法1

function 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)。

方法2

function 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)