招聘季节一般都在金三银四,或者金九银十。最近在这五六月份,陆陆续续面试了十几个高级前端。有一套考察算法的小题目。后台返回一个扁平的数据结构,转成树。
我们看下题目:打平的数据内容如下:
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)
- k次方阶
O(n^K)
- 指数阶
O(2^n)
通常我们计算时间复杂度都是计算最坏情况。计算时间复杂度的要注意的几个点
- 如果算法的执行时间
不随n
的增加
而增长
,假如算法中有上千条
语句,执行时间也不过是一个较大的常数
。此类算法的时间复杂度是O(1)
。 举例如下:代码执行100次,是一个常数,复杂度也是O(1)
。
letx = 1
while (x 复制代码
- 有
多个循环语
句时候,算法的时间复杂度是由嵌套层数最多
的循环语句中最内层
语句的方法决定的。举例如下:在下面for循环当中,外层循环
每执行一次
,内层循环
要执行n
次,执行次数是根据n所决定的,时间复杂度是O(n^2)
。
for (i = 0
for (j = 0
// ...code
}
}
复制代码
- 循环不仅与
n
有关,还与执行循环判断条件
有关。举例如下:在代码中,如果arr[i]
不等于1
的话,时间复杂度是O(n)。如果arr[i]
等于1
的话,循环不执行,时间复杂度是O(0)
。
for(var i = 0; i[i] !=1; i++) {
// ...code
}
复制代码
空间复杂度是对一个算法在运行过程中临时占用存储空间的大小。
计算空间复杂度的简单几点
- 仅仅只复制单个变量,空间复杂度为O(1)。举例如下:空间复杂度为O(n) = O(1)。
leta = 1
let b = 2
let c = 3
console.log('输出a,b,c', a, b, c)
复制代码
- 递归实现,调用fun函数,每次都创建1个变量k。调用n次,空间复杂度O(n*1) = O(n)。
functionfun(n) {
let k = 10;
if (n == k) {
return n;
} else {
return fun(++n)
}
}
复制代码
不考虑性能实现,递归遍历查找
主要思路是提供一个递 getChildren
的方法,该方法 递归
去查找子集。 就这样,不用考虑性能,无脑去查,大多数人只知道递归,就是写不出来。。。
/**
* 递归查找,获取children
*/
constgetChildren = (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) {
constresult = []
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) {
constresult = []
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、 关注我,让我们成为长期关系
3、关注公众号「 前端有话说」,里面已有多篇原创文章,和开发工具,欢迎各位的关注,第一时间阅读我的文章
Original: https://blog.csdn.net/china_coding/article/details/128392157
Author: china_coding
Title: 面试了十几个高级前端,竟然连(扁平数据结构转Tree)都写不出来
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/777880/
转载文章受原作者版权保护。转载请注明原作者出处!