招聘季节一般都在金三银四,或者金九银十。最近在这五六月份,陆陆续续面试了十几个高级前端。有一套考察算法的小题目。后台返回一个扁平的数据结构,转成树。
我们看下题目:打平的数据内容如下:
let arr = [ {id: 1, name: '部门1', pid: 0}, {id: 2, name: '部门2', pid: 1}, {id: 3, name: '部门3', pid: 1}, {id: 4, name: '部门4', pid: 3}, {id: 5, name: '部门5', pid: 4}, ]
输出结果
[ { "id": 1, "name": "部门1", "pid": 0, "children": [ { "id": 2, "name": "部门2", "pid": 1, "children": [] }, { "id": 3, "name": "部门3", "pid": 1, "children": [ ] } ] } ]
我们的要求很简单,可以先不用考虑性能问题。实现功能即可,回头分析了面试的情况,结果使我大吃一惊。
10%的人没思路,没碰到过这种结构
60%的人说用过递归,有思路,给他个笔记本,但就是写不出来
20%的人在引导下,磕磕绊绊能写出来
剩下10%的人能写出来,但性能不是最佳
感觉不是在招聘季节遇到一个合适的人真的很难。
接下来,我们用几种方法来实现这个小算法
判断一个算法的好坏,一般从 执行时间
和 占用时间
来看,执行时间越短,占用的内存空间越小,那么它就是好的算法。对应的,我们常常用时间复杂度代表执行时间,空间复杂度代表占用的内存空间。
时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的次数。 随着
n
的不断增大
,时间复杂度不断增大
,算法花费时间
越多。 常见的时间复杂度有
O(1)
O(log2 n)
O(n)
O(n log2 n)
O(n^2)
O(n^3)
O(n^K)
O(2^n)
通常我们计算时间复杂度都是计算最坏情况。计算时间复杂度的要注意的几个点
let x = 1 while (x
for (i = 0 for (j = 0 // ...code } }
for(var i = 0; i[i] !=1; i++) { // ...code }
空间复杂度是对一个算法在运行过程中临时占用存储空间的大小。
计算空间复杂度的简单几点
let a = 1 let b = 2 let c = 3 console.log('输出a,b,c', a, b, c)
function fun(n) { let k = 10; if (n == k) { return n; } else { return fun(++n) } }
主要思路是提供一个递 getChildren
的方法,该方法 递归
去查找子集。 就这样,不用考虑性能,无脑去查,大多数人只知道递归,就是写不出来。。。
/** * 递归查找,获取children */ const getChildren = (data, result, pid) => { for (const item of data) { if (item.pid === pid) { const newItem = {...item, children: []} result.push(newItem) getChildren(data, newItem.children, item.id) } } } /** * 转换方法 */ const arrayToTree = (data, pid) => { const result = [] getChildren(data, result, pid) return result }
从上面的代码我们分析,该实现的时间复杂度为 O(2^n)
。
主要思路是先把数据转成 Map
去存储,之后遍历的同时借助 对象的引用
,直接从 Map
找对应的数据做存储
function arrayToTree(items) { const result = [] const itemMap = {} // 先转成map存储 for (const item of items) { itemMap[item.id] = {...item, children: []} } for (const item of items) { const id = item.id const pid = item.pid const treeItem = itemMap[id] if (pid === 0) { result.push(treeItem) } else { if (!itemMap[pid]) { itemMap[pid] = { children: [], } } itemMap[pid].children.push(treeItem) } } return result }
从上面的代码我们分析,有两次循环,该实现的时间复杂度为 O(2n)
,需要一个Map把数据存储起来,空间复杂度 O(n)
function arrayToTree(items) { const result = [] const itemMap = {} for (const item of items) { const id = item.id const pid = item.pid if (!itemMap[id]) { itemMap[id] = { children: [], } } itemMap[id] = { ...item, children: itemMap[id]['children'] } const treeItem = itemMap[id] if (pid === 0) { result.push(treeItem) } else { if (!itemMap[pid]) { itemMap[pid] = { children: [], } } itemMap[pid].children.push(treeItem) } } return result }
从上面的代码我们分析,一次循环就搞定了,该实现的时间复杂度为 O(n)
,需要一个Map把数据存储起来,空间复杂度 O(n)
方法1000(条)10000(条)20000(条)50000(条)递归实现154.596ms1.678s7.152s75.412s不用递归,两次遍历0.793ms16.499ms45.581ms97.373ms不用递归,一次遍历0.639ms6.397ms25.436ms44.719ms
从我们的测试结果来看,随着数量的增大,递归的实现会越来越慢,基本成指数的增长方式。
大家觉得高级前端,该不该很顺利的把这个给写出来。评论区留下你的见解。有比以上更好的实现,评论区留下你的答案,大家一起学习。
如果你觉得该文章不错,不妨
1、 点赞,让更多的人也能看到这篇内容
2、 关注我,让我们成为长期关系
本文作者:前端小毛
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!