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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1581 天前的主题，其中的信息可能已经有所发展或是发生改变。

// 输入
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

2020-08-02 18:26:35 +08:00

按照数组长度从大到小，每次看是不是之前数组的子集

crclz

2020-08-02 18:40:56 +08:00

笨办法

musi

2020-08-02 18:46:51 +08:00

`
data.filter((value, index, arr) => !arr.some((a, idx) => index != idx && value.every(val => a.includes(val))))
`

einq7

2020-08-02 19:07:57 +08:00

@musi 厉害，，对比自己之前写的一坨，自己差了好多

SakuraSa

2020-08-02 19:12:00 +08:00

创建前缀树，然后再遍历叶子节点输出路径？时间复杂度 O(n)空间复杂度 O(n)

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

2020-08-02 19:52:46 +08:00

@SakuraSa 感谢分享！我去看看

VDimos

2020-08-02 20:04:43 +08:00 via Android

排序加哈希编码？

lithbitren

2020-08-03 12:24:45 +08:00

数据量不大的话就暴力 includes，时间复杂度最优应该还是前缀树

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;
}
```