-
Notifications
You must be signed in to change notification settings - Fork 3.3k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
第 88 题:实现 convert 方法,把原始 list 转换成树形结构,要求尽可能降低时间复杂度 #139
Comments
function convert(list) {
const res = []
const map = list.reduce((res, v) => (res[v.id] = v, res), {})
for (const item of list) {
if (item.parentId === 0) {
res.push(item)
continue
}
if (item.parentId in map) {
const parent = map[item.parentId]
parent.children = parent.children || []
parent.children.push(item)
}
}
return res
} 时间复杂度O(n) |
基本思路: const convert = list => {
let map = new Map();
let result = []
list.forEach(el => {
map.set(el.id, el);
});
list.forEach(el => {
let parent = map.get(el.parentId);
if (!parent) {
// parentId === 0
el.children = []
return
}
if (parent.hasOwnProperty('children')) {
parent.children.push(el);
} else {
parent['children'] = [];
parent.children.push(el);
}
});
for (let i = 0; i < list.length; i++) {
const el = list[i];
if (el.parentId === 0) {
result.push(el)
}
}
return result
};
let list = [
{ id: 1, name: '部门A', parentId: 0 },
{ id: 2, name: '部门B', parentId: 0 },
{ id: 3, name: '部门C', parentId: 1 },
{ id: 4, name: '部门D', parentId: 1 },
{ id: 5, name: '部门E', parentId: 2 },
{ id: 6, name: '部门F', parentId: 3 },
{ id: 7, name: '部门G', parentId: 2 },
{ id: 8, name: '部门H', parentId: 4 }
];
convert(list) |
function convert(arr) {
const obj = {}
const res = []
list.forEach(item => {
obj[item.id] = item
})
list.forEach(item => {
if (item.parentId !== 0) {
obj[item.parentId]['children'] ? obj[item.parentId]['children'].push(item) : obj[item.parentId]['children'] = [item]
} else {
res.push(item)
}
})
return res
} |
function convert(list) { |
两轮遍历,时间复杂度 O(n^2) 😂 function convert(arr) {
let tree = [];
arr.map((it, idx, array) => {
let parent = it.parentId;
if (parent === 0) { // 根节点
tree.push(it);
} else {
array.map(item => {
if (item.id === parent) {
if (!item.children) {
item.children = [];
}
item.children.push(it);
}
});
}
});
return tree;
} |
|
const convert = (list) => {
} |
大佬看看我的? |
|
@
这个算不上O(n)吧 |
难度的话O(n*2)左右 |
这就是O(n)啊, 第一次遍历生成哈希表扫描了一次,然后再扫描了一次list,总共进行了2n次操作,时间复杂度是O(2n) = O(n) |
|
基于DFS来写 function convert(source, parentId = 0){
let trees = [];
for (let item of source) {
if(item.parentId === parentId) {
let children = convert(source, item['id']);
if(children.length) {
item.children = children
}
trees.push(item);
}
}
return trees;
}
let list =[
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
const result = convert(list);
|
function convert(list){ |
如果这两个是嵌套循环就是n^2, 代码里面明显是两次,而不是嵌套的 |
for of里面不是包括了for in 吗? |
|
一次循环解决 function convert(list) {
const cache = new Map()
return list.reduce((res, cur) => {
const { id, parentId } = cur
const item = { ...cur }
if (parentId === 0) {
res.push(item)
} else {
const itemCache = cache.get(parentId)
!itemCache.children && (itemCache.children = [])
itemCache.children.push(item)
}
cache.set(id, item)
return res
}, []);
} |
|
用递归试试 function convert(array , parentId=0){
let result = []
array.forEach((item,index)=>{
if(item.parentId === parentId){
let children = convert(array,item.id);
if(children.length>0){
item.children = children ;
}
result.push(item);
}
})
return result;
} |
看了大佬们写的用map要好一些 |
function convert(list) {
let m = new Map()
return list.reduce((pre,cur)=>{
m.set(cur.id,cur)
let parent = m.get(cur.parentId)
if( parent){
(parent.children || (parent.children = [])).push(cur)
return pre
}
return [...pre,cur]
},[])
} 这么多人写了我就随便再写个吧,时间复杂度 O(n) |
/*
转换成树形结构
思路:
1、构造一个id与对象的对应关系
2、循环变价原数组,将item放在指定的parent之下
3、循环字典,找出parentId === 0的对象即可
****一共3遍遍历3*O(n)*****
*/
function convert (list) {
let arr = [];
let dict = {};
list.forEach(item => {
dict[item.id] = item;
})
list.forEach(item => {
if(item.parentId) {
let children = dict[item.parentId].children;
if (children) {
dict[item.parentId].children.push(item)
} else {
dict[item.parentId].children = [item];
}
}
})
for(let key in dict) {
if(dict[key].parentId === 0) {
arr.push(dict[key])
}
}
return arr;
}
let list =[
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
let res = convert(list);
console.log(res) |
有大佬看看我的吗 |
|
加了个map记录parent的路径,这个循环一次。
|
这个的时间复杂度为什么不是2*O(n) |
function convert(list) {
const map = {};
const res = [];
list.forEach((item) => {
const obj = {
id: item.id,
name: item.name,
parentId: 0,
};
if (map[item.id]) { // 之前简单生成的数据没有name和parentId,此时添加上
map[item.id].name = item.name;
map[item.id].parentId = item.parentId;
} else {
map[item.id] = obj;
}
if (item.parentId === 0) {
res.push(map[item.id]);
} else {
if (map[item.parentId]) {
map[item.parentId].children = map[item.parentId].children
? map[item.parentId].children.concat(map[item.id])
: [map[item.id]];
} else {
// 如果此时对于的parentId部门在map中没有对于值,先简单生成
map[item.parentId] = {
id: item.parentId,
children: [map[item.id]],
};
}
}
});
return res;
} O(n)时间复杂度,边遍历编生成map,可以处理顺序不对的情况 const list = [
{ id: 3, name: '部门C', parentId: 1 }, // 此时部门1还没有生成,
{ id: 1, name: '部门A', parentId: 0 },
{ id: 2, name: '部门B', parentId: 0 },
{ id: 4, name: '部门D', parentId: 1 },
{ id: 5, name: '部门E', parentId: 2 },
{ id: 6, name: '部门F', parentId: 3 },
{ id: 7, name: '部门G', parentId: 2 },
{ id: 8, name: '部门H', parentId: 4 },
]; |
|
function convert(data) {
const idMapping = data.reduce((acc, cur, index) => {
acc[cur.id] = index
return acc
}, {})
const arr = []
data.forEach(el => {
if (el.parentId === 0) {
arr.push(el)
return
}
const parentEl = data[idMapping[el.parentId]]
parentEl.children = [...(parentEl.children || []), el]
})
return arr
} |
const listToTree = (tree) => {
const map = tree.reduce((map, crt) => (map[crt.id] = crt, crt.children = [], map), {})
return tree.filter(node => {
node.parentId && map[node.parentId].children.push(node)
return !node.parentId
})
} |
let list = [
{ id: 1, name: '部门A', parentId: 0 },
{ id: 2, name: '部门B', parentId: 0 },
{ id: 3, name: '部门C', parentId: 1 },
{ id: 4, name: '部门D', parentId: 1 },
{ id: 5, name: '部门E', parentId: 2 },
{ id: 6, name: '部门F', parentId: 3 },
{ id: 7, name: '部门G', parentId: 2 },
{ id: 8, name: '部门H', parentId: 4 },
{ id: 9, name: '部门I', parentId: 10 },
];
const result = convert(list);
function convert(list) {
list = list.sort((a, b) => a.parentId - b.parentId);
let i = list.length - 1;
while (i > 0) {
const item = list[i];
const parent = list.find(itm => itm.id === item.parentId);
if (parent) {
parent.children = parent.children || [];
parent.children.push(item);
list.splice(i, 1);
}
i--;
}
return list;
}
console.log(result); |
一次遍历搞定 function convert(list) {
const root = {
children: []
};
const map = {
0: root
};
for (let item of list) {
const { id, name, parentId } = item;
const current = map[id] || (map[id] = {
children: []
})
current.id = id;
current.name = name;
const parent = map[parentId] || (map[parentId] = {
children: []
})
parent.children.push(current);
}
return root.children;
} |
***@***.*** added you to their Edison Mail+ Family Plan
***@***.*** added you to their Edison Mail+ Family Plan
Welcome to the family! Access your new Edison Mail+ premium email features by connecting this email
account to the Edison Mail app. You will continue to have free access as long as ***@***.***
has an active Plus subscription.
Maximize your email security, block spam calls, and more!
Don't have the app?
|
const convert=(list)=>{
const map={};
const result=[];
for (let index = 0; index < list.length; index++) {
map[list[index].id]=list[index]
}
for (let index = 0; index < list.length; index++) {
const element = list[index];
if(element.parentId==0){
result.push(element)
}else{
if(element.parentId in map){
if(map[element.parentId].children){
map[element.parentId].children.push(element)
}else{
map[element.parentId].children=[element]
}
}
}
}
return result
} |
/**
* record := {}
* i := 0
* while i < list.length
* if record[list[i].parentId] == null
* record[list[i].parentId] := [];
* end if
* record[list[i].parentId].push(list[i]);
* i += 1
* i := 0
* res := []
* while i < list.length
* treeNode := list[i]
* if treeNode.parentId === 0
* res.push(treeNode)
* end if
* children := record[treeNode.id] || []
* treeNode.children = children
* i += 1
* return res
*/
const solution = (list) => {
const record = list.reduce((res, node, idx) => {
if (!res[node.parentId]) res[node.parentId] = [];
res[node.parentId].push(list[idx]);
return res;
}, {});
let res = [];
list.forEach((ele) => {
const treeNode = ele;
if (treeNode.parentId === 0) res.push(treeNode);
treeNode.children = record[treeNode.id] || [];
});
return res;
};
let list = [
{ id: 1, name: "部门A", parentId: 0 },
{ id: 2, name: "部门B", parentId: 0 },
{ id: 3, name: "部门C", parentId: 1 },
{ id: 4, name: "部门D", parentId: 1 },
{ id: 5, name: "部门E", parentId: 2 },
{ id: 6, name: "部门F", parentId: 3 },
{ id: 7, name: "部门G", parentId: 2 },
{ id: 8, name: "部门H", parentId: 4 }
];
solution(list);
|
const convert = list => {
for (let i = 0, length = list.length; i < length; i++) {
const el = list[i];
el.children = el.children || [];
let index = list.findIndex(v => v.id == el.parentId);
if (index !== -1) {
list[index].children.push(el);
}
}
return list.filter(v => v.parentId == 0);
}; 这样有什么问题吗 |
这样好像会影响到原 list,最好在 convert 方法中深拷贝一下(个人用的是 JSON.parse(JSON.stringify(source.list)) |
dfs
|
let list = [
{id: 1, name: '部门A', parentId: 0 },
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
function convert(list, rootId) {
return list.reduce((res, curr) => {
if (curr.parentId === rootId) {
curr.children = convert(list.filter(item => item.parentId !== rootId), curr.id)
res.push(curr)
}
return res
}, [])
}
console.log(convert(list, 0)) |
let list = [{
id: 1,
name: '部门A',
parentId: 0
}, {
id: 2,
name: '部门B',
parentId: 0
}, {
id: 3,
name: '部门C',
parentId: 1
}, {
id: 4,
name: '部门D',
parentId: 1
}, {
id: 5,
name: '部门E',
parentId: 2
}, {
id: 6,
name: '部门F',
parentId: 3
}, {
id: 7,
name: '部门G',
parentId: 2
}, {
id: 8,
name: '部门H',
parentId: 4
}];
function convert(list = []) {
if (list.length) {
const res = {}
for (const val of list) {
if (!res[val.id]) {
res[val.id] = val
}
if (res[val.parentId]) {
if (!res[val.parentId].children) {
res[val.parentId].children = []
}
res[val.parentId].children.push(val)
}
}
return res
}
}
console.log(convert(list)); |
如果list的数据是这样的,就得不到正确结果了 let list =[
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:8,name:'部门H',parentId:4}
]; |
interface Department {
id: number
name: string
parentId: number
}
interface TreeDepartment {
id: number
name: string
parentId: number
children?: TreeDepartment[]
}
function convert(list: Department[]): TreeDepartment[] {
const result: TreeDepartment[] = []
const idMap = new Map<number, TreeDepartment>()
list.forEach(item => {
const node = idMap.get(item.id)
const nodeChildren = node?.children
const params: TreeDepartment = { ...item }
if (nodeChildren) {
params.children = nodeChildren
}
idMap.set(item.id, params)
if (item.parentId === 0) {
result.push(params)
return
}
const parentNode = idMap.get(item.parentId)
if (parentNode) {
parentNode.children
? parentNode.children.push(params)
: (parentNode.children = [params])
} else {
idMap.set(item.parentId, {
children: [params]
} as TreeDepartment)
}
})
return result
}
const list = [
{ id: 1, name: '部门A', parentId: 0 },
{ id: 2, name: '部门B', parentId: 0 },
{ id: 3, name: '部门C', parentId: 1 },
{ id: 4, name: '部门D', parentId: 1 },
{ id: 5, name: '部门E', parentId: 2 },
{ id: 6, name: '部门F', parentId: 3 },
{ id: 7, name: '部门G', parentId: 2 },
{ id: 8, name: '部门H', parentId: 4 }
]
const result = convert(list)
console.dir(result, { depth: null }) |
let list = [
{id: 1, name: '部门A', parentId: 0 },
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
function convert(list) {
let result = {};
const root = 0;
list.forEach((item) => {
const { id, parentId } = item;
if (result[id]) {
result[id] = { ...result[id], ...item };
} else {
result[id] = { ...item, child: [] };
}
const parent = parentId
if (result[parent]) {
result[parent].child.push(result[id]);
} else {
result[parent] = { id: parent, child: [result[id]] };
}
});
return result[root].child;
}
console.log(convert(list)); 时间复杂度: O(n); |
function convert(list) {
const map = new Map(); // 借用对象内存指针指向堆
return list.reduce((pre, cur) => {
const { id, parentId } = cur;
if (parentId === 0) {
pre.push(cur);
} else {
const itemCache = map.get(parentId);
if (itemCache) {
itemCache.children = itemCache.children ? [...itemCache.children, cur] : [cur];
}
}
if (!map.has(id)) {
map.set(id, cur);
}
return pre;
}, []);
} |
function convert(list, pid) { |
export function flatArrToTree (arr: Array<object>): Array<any> {
// 建立关系表
const map = createCorrelationMap(arr)
// 生成树形结构
const result = createTree(arr, map)
return result
}
function createCorrelationMap (arr: Array<object>): object {
// 建立关系表
const map = {}
arr.forEach((item: any) => {
map[item.id] = item
map[item.id].children = []
})
return map
}
function createTree (arr: Array<object>, map: object): Array<any> {
const result = []
arr.forEach((item: any) => {
if (item.pid == 0) {
// pid 为零直接作为根节点
result.push(item)
} else {
// 不为零查询当前数据的父节点
const paraent = map[item.pid]
paraent.children.push(item)
}
})
return result
} |
您好,已收到你的邮件,有空的话我会尽快去查看。
----
Hi,I am busy and will check your email soon,best regard!
陈建才Colin Chen
|
function converTree(arr) {
const tree = []
const treeMap = {}
while(arr.length) {
const target = arr.shift()
treeMap[target.id] = target
if (target.parentId === 0) {
tree.push(target)
continue
}
if (treeMap[target.parentId]) {
(treeMap[target.parentId].children || (treeMap[target.parentId].children = [])).push(target)
}
}
return tree
} |
const treeOrganization = orgList => {
const treeList = [];
for (const org of orgList) {
if (!recursiveTraverse(treeList, findInsertFn(org))) {
org.children = [];
treeList.push(org);
}
}
return treeList;
}
const findInsertFn = current => node => {
if (node.id === current.parentId) {
current.children = [];
node.children = [...node.children, current];
return true;
}
return false;
}
const recursiveTraverse = (nodeList, findCallback) => {
for (const node of nodeList) {
if (findCallback(node)) {
return true;
}
if (recursiveTraverse(node.children, findCallback)) {
return true;
}
}
return false;
}
let orgList =[
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
const treeList = treeOrganization(orgList);
console.log(JSON.stringify(treeList, null, 2)); |
|
// O(n) |
function convert(list) { |
提供俩种写法,欢迎大家来看 function convert2(arr){ |
如果有断层或者不规律的数据会有遗漏 const list=[ |
const arrToTree = (list: any) => { |
function convert(arr) {
const map = {};
const result = [];
for (let item of arr) {
const { id, parentId, name } = item;
if (map[id]) {
map[id].name = name;
map[id].parentId = parentId;
} else {
map[id] = Object.assign({ children: [] }, item);
}
if (parentId === 0) {
result.push(map[id]);
} else {
if (map[parentId]) {
map[parentId].children.push(map[id]);
} else {
map[parentId] = {
id: parentId,
children: [map[id]],
};
}
}
}
return result;
}
console.log(
convert([
{ id: 1, name: "部门A", parentId: 0 },
{ id: 2, name: "部门B", parentId: 0 },
{ id: 3, name: "部门C", parentId: 1 },
{ id: 4, name: "部门D", parentId: 1 },
{ id: 5, name: "部门E", parentId: 2 },
{ id: 6, name: "部门F", parentId: 3 },
{ id: 7, name: "部门G", parentId: 2 },
{ id: 8, name: "部门H", parentId: 4 },
])
); |
以下数据结构中,id 代表部门编号,name 是部门名称,parentId 是父部门编号,为 0 代表一级部门,现在要求实现一个 convert 方法,把原始 list 转换成树形结构,parentId 为多少就挂载在该 id 的属性 children 数组下,结构如下:
The text was updated successfully, but these errors were encountered: