// 输入
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"],
]
小弟在线求指导
1
QingchuanZhang 2020-08-02 18:26:35 +08:00
按照数组长度从大到小,每次看是不是之前数组的子集
|
2
crclz 2020-08-02 18:40:56 +08:00
笨办法
|
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)))) ` |
5
SakuraSa 2020-08-02 19:12:00 +08:00
创建前缀树,然后再遍历叶子节点输出路径?时间复杂度 O(n)空间复杂度 O(n)
|
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)); ``` |
8
VDimos 2020-08-02 20:04:43 +08:00 via Android
排序加哈希编码?
|
9
lithbitren 2020-08-03 12:24:45 +08:00
数据量不大的话就暴力 includes,时间复杂度最优应该还是前缀树
|
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; } ``` |