扁平化
面试题
手写数组扁平化 flatten,并扩展说明对象扁平化怎么做
面试官视角
这题通常从数组扁平化开始,追问点包括:
- 是否支持指定深度
- 是否会改变原数组
- 是否能不用
Array.prototype.flat - 如果数组层级很深,递归会不会栈溢出
- 对象扁平化时怎么处理 key 路径
数组扁平化
核心思路
遍历数组,如果当前项还是数组,并且还可以继续展开,就递归展开;否则直接放进结果数组
- 定义结果数组
result - 遍历原数组
- 如果元素是数组,并且
depth > 0,递归扁平化 - 否则把当前元素放进结果
- 返回结果数组,不修改原数组
递归实现
function flatten(arr, depth = Infinity) {
const result = []
for (const item of arr) {
if (Array.isArray(item) && depth > 0) {
result.push(...flatten(item, depth - 1))
} else {
result.push(item)
}
}
return result
}验证:
console.log(flatten([1, [2, [3, [4]]]], 1))
// [1, 2, [3, [4]]]
console.log(flatten([1, [2, [3, [4]]]]))
// [1, 2, 3, 4]reduce 实现
function flatten(arr, depth = Infinity) {
return arr.reduce((result, item) => {
if (Array.isArray(item) && depth > 0) {
result.push(...flatten(item, depth - 1))
} else {
result.push(item)
}
return result
}, [])
}非递归实现
如果面试官追问"层级很深递归爆栈怎么办",可以写栈版本
function flatten(arr) {
const stack = [...arr]
const result = []
while (stack.length > 0) {
const item = stack.pop()
if (Array.isArray(item)) {
stack.push(...item)
} else {
result.push(item)
}
}
return result.reverse()
}对象扁平化
对象扁平化一般是把嵌套对象变成路径 key:
const obj = {
a: {
b: 1,
c: [2, 3]
}
}
// {
// 'a.b': 1,
// 'a.c[0]': 2,
// 'a.c[1]': 3
// }实现
function flattenObject(obj) {
const result = {}
function dfs(value, path) {
if (value !== null && typeof value === 'object') {
if (Array.isArray(value)) {
value.forEach((item, index) => {
dfs(item, `${path}[${index}]`)
})
return
}
Object.keys(value).forEach((key) => {
const nextPath = path ? `${path}.${key}` : key
dfs(value[key], nextPath)
})
return
}
result[path] = value
}
dfs(obj, '')
return result
}面试回答模板
数组扁平化的本质是深度优先遍历。遇到普通元素就加入结果,遇到数组就继续展开,并通过 depth 控制展开层级。递归版本代码最直观,但层级特别深可能爆栈,可以改成显式栈迭代。对象扁平化也是 DFS,只是遍历过程中要维护当前路径
易错点
depth = 0时不能继续展开- 递归实现不要修改原数组
- 非递归栈版本因为用
pop,最终要reverse保持顺序 - 对象扁平化要区分数组路径和对象路径
null的typeof是'object',要单独排除
