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

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

  •  
  •   einq7 · 2020-08-02 18:20:18 +08:00 · 1881 次点击
    这是一个创建于 1334 天前的主题,其中的信息可能已经有所发展或是发生改变。
    // 输入
    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  
       2020-08-02 18:26:35 +08:00
    按照数组长度从大到小,每次看是不是之前数组的子集
    crclz
        2
    crclz  
       2020-08-02 18:40:56 +08:00
    笨办法
    musi
        3
    musi  
       2020-08-02 18:46:51 +08:00   ❤️ 1
    `
    data.filter((value, index, arr) => !arr.some((a, idx) => index != idx && value.every(val => a.includes(val))))
    `
    einq7
        4
    einq7  
    OP
       2020-08-02 19:07:57 +08:00
    @musi 厉害,,对比自己之前写的一坨,自己差了好多
    SakuraSa
        5
    SakuraSa  
       2020-08-02 19:12:00 +08:00
    创建前缀树,然后再遍历叶子节点输出路径?时间复杂度 O(n)空间复杂度 O(n)
    SakuraSa
        6
    SakuraSa  
       2020-08-02 19:34:11 +08:00
    ```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  
    OP
       2020-08-02 19:52:46 +08:00
    @SakuraSa 感谢分享!我去看看
    VDimos
        8
    VDimos  
       2020-08-02 20:04:43 +08:00 via Android
    排序加哈希编码?
    lithbitren
        9
    lithbitren  
       2020-08-03 12:24:45 +08:00
    数据量不大的话就暴力 includes,时间复杂度最优应该还是前缀树
    AboveYunhai
        10
    AboveYunhai  
       2020-08-04 09:11:52 +08:00
    @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;
    }
    ```
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3092 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 12:52 · PVG 20:52 · LAX 05:52 · JFK 08:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.