首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
einq7
V2EX  ›  程序员

二维数组中如何去除有被其他数组元素包含的元素

  •  
  •   einq7 · 9 天前 · 786 次点击
    // 输入
    const data = [
      ["root", "system", "synchronization-logs"],
      ["root", "system", "synchronization-configs"],
      ["root", "system"],
      ["root", "configs"],
      ["root"],
    ];
    
    // 期望输出
    const output = [
      ["root", "system", "synchronization-logs"],
      ["root", "system", "synchronization-configs"],
      ["root", "configs"],
    ]
    

    小弟在线求指导

    10 条回复    2020-08-04 09:11:52 +08:00
    QingchuanZhang
        1
    QingchuanZhang   9 天前
    按照数组长度从大到小,每次看是不是之前数组的子集
    crclz
        2
    crclz   9 天前
    笨办法
    musi
        3
    musi   9 天前   ❤️ 1
    `
    data.filter((value, index, arr) => !arr.some((a, idx) => index != idx && value.every(val => a.includes(val))))
    `
    einq7
        4
    einq7   9 天前
    @musi 厉害,,对比自己之前写的一坨,自己差了好多
    SakuraSa
        5
    SakuraSa   9 天前
    创建前缀树,然后再遍历叶子节点输出路径?时间复杂度 O(n)空间复杂度 O(n)
    SakuraSa
        6
    SakuraSa   9 天前
    ```js
    const data = [
    ["root", "system", "synchronization-logs"],
    ["root", "system", "synchronization-configs"],
    ["root", "system"],
    ["root", "configs"],
    ["root"],
    ];


    function filter_file_path(path_list) {
    // build perfixes tree
    let root = {'__size__': 0};
    data.forEach(path => {
    var state = {'node': root};
    path.forEach(part => {
    if (state.node[part] === undefined) {
    state.node[part] = {'__size__': 0};
    state.node.__size__ ++;
    }
    state.node = state.node[part];
    });
    });

    // filter out non-leaf node path
    return data.filter(path => {
    var state = {
    'node': root
    };
    path.forEach(part => {
    state.node = state.node[part];
    });
    return state.node.__size__ === 0;
    });
    }

    console.log(filter_file_path(data));
    ```
    einq7
        7
    einq7   9 天前
    @SakuraSa 感谢分享!我去看看
    VDimos
        8
    VDimos   9 天前 via Android
    排序加哈希编码?
    lithbitren
        9
    lithbitren   9 天前
    数据量不大的话就暴力 includes,时间复杂度最优应该还是前缀树
    AboveYunhai
        10
    AboveYunhai   8 天前
    @SakuraSa @einq7 前缀树代码有些 bug 和部分情况没有处理,而且可以在建立前缀树的时候同时对数据进行处理,这样数据只需要走一遍了,只修改了一点同时减少了代码量。

    ```js
    function filter_file_path(path_list) {
    // build perfixes tree
    let root = {'__size__': 0};
    var output = [];
    path_list.forEach(path => {
    var state = {'node': root};
    var update = false;
    path.forEach(part => {
    if (state.node[part] === undefined) {
    update=true;
    state.node[part] = {'__size__': 0};
    state.node.__size__ ++;
    }
    state.node = state.node[part];
    });
    //new tree, add to output list
    if(update === true) {
    output.push(path);
    update=false;
    }
    });
    return output;
    }
    ```
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4237 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 06:37 · PVG 14:37 · LAX 23:37 · JFK 02:37
    ♥ Do have faith in what you're doing.