面试官：你知道几种数组扁平化的方法？

站长

2024年03月29日 21:27 · 阅读数 2

唠一唠

数组扁平化相信不少掘友在一些面试中被问到过，这在我们日常编程中也是一个常规操作，它需要我们将一个多维数组转化成一个一维数组。当然，我相信很多掘友都能回答上这个问题，但如果面试官要我们多回答几种，可能有些掘友就答不上来了，所以，借着这篇文章，我们今天就一起来汇总一下几种数组扁平化的方式。

1. 普通递归方法

相信掘友们首先能想到的实现数组扁平化解法是使用递归函数。该方法通过遍历数组中的每个元素，检查它是否还是一个数组。如果是，则对子数组进行同样的扁平化操作，并将结果合并到最终的一维数组中。例如：

let arr = [1,2,[3,4,[5,6]]]

function flattenArray(arr) {
  let result = []
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      result = result.concat(flattenArray(arr[i]));
    } else {
      result.push(arr[i])
    }
  }
  return result
}

console.log(flattenArray(arr));  // [ 1, 2, 3, 4, 5, 6 ]

2. reduce() 方法

利用Array.prototype.reduce()函数的累加器特性，遍历数组并将子数组扁平化后的结果合并到最终的一维数组中。其实也是递归，不过不像上面一样用for循环，和上面代码差别不大，这里主要是利用了reduce方法，代码书写起来更简洁。

let arr = [1,2,[3,4,[5,6,[7,8]]]]

function flattenWithReduce(arr) {
  return arr.reduce((acc, val) => 
    acc.concat(Array.isArray(val) ? flattenWithReduce(val) : [val]),
    []
  );
}

console.log(flattenWithReduce(arr)) // [1, 2, 3, 4, 5, 6, 7, 8]

优点：可读性强，逻辑清晰，无需额外创建函数闭包。缺点：对于非常深的嵌套结构，性能可能不如使用flat()方法。

3. Array.prototype.flat()

ES6引入了flat()方法，可以直接对数组进行扁平化操作，可以指定扁平化的层级深度。

let arr = [1,2,[3,4,[5,6,[7,8,[9]]]]]

function flattenWithFlat(arr) {
  return arr.flat(Infinity) // Infinity表示完全扁平化所有层级
}

console.log(flattenWithFlat(arr)) // [1,2,3,4,5,6,7,8,9]

优点：简洁高效，原生支持，适合现代浏览器环境。缺点：旧版浏览器不支持此方法，需要polyfill或其他兼容方案。

4. 扩展运算符与concat

利用扩展运算符（...）和concat()结合，逐步展开嵌套数组。

let arr = [1,2,[3,[4],[5,6,[7,8,[9]]]]]

function flattenWithSpread(arr) {
  while (arr.some(item => Array.isArray(item))) {
    arr = [].concat(...arr)
  }
  return arr
}

console.log(flattenWithSpread(arr)); // [1,2,3,4,5,6,7,8,9]

优点：代码相对简洁，易于理解。缺点：循环执行次数取决于数组嵌套深度，效率相对较低。

5. 广度优先搜索与队列

该方法采用广度优先搜索，也就是我们常说的BFS策略来扁平化嵌套数组。首先创建一个队列并将原数组作为初始节点入队。然后进入循环阶段，只要队列不为空，就从队列头部取出一层元素（即当前层级的所有子数组或值），并检查每个元素是否为数组。如果是数组，则将其元素逐个加入队列后部；如果不是数组，则直接将值加入结果数组中。循环直至队列为空，此时结果数组中包含了所有已展开的一维元素。

let arr = [1,2,[3,[4],[5,6,[7,8,[9]]]]]

function flattenWithBFS(arr) {
  const queue = [arr] // 创建队列，初始化为待处理的数组
  const result = [] 

  while (queue.length > 0) { 
    const levelItems = queue.shift() // 取出队列首部的一层元素
    for (const item of levelItems) { // 遍历当前层级的每个元素
      if (Array.isArray(item)) { 
        queue.push(item); 
      } else {
        result.push(item) 
      }
    }
  }

  return result 
}

console.log(flattenWithBFS(arr)) // [1,2,3,4,5,6,7,8,9]

优点：

空间效率较高：通过使用队列结构进行层次遍历，能够保证在有限的循环次数内完成对任何深度嵌套数组的扁平化。
无需递归调用栈：相比于递归方法，这种方法避免了因深层嵌套导致的栈溢出问题。

缺点：

时间复杂度：尽管比扩展运算符结合concat()的方法有所改进，但在极端情况下（例如，非常深且宽的树形结构），仍需多次迭代才能完全扁平化数组。
代码相对复杂：相较于简单的扩展运算符与concat()结合的方式，此方法涉及队列操作，理解起来可能需要更多时间。

6. 深度优先搜索与堆栈

该方法利用了堆栈数据结构进行深度优先搜索，也就是DFS。首先将待处理的原数组转换为堆栈，并创建一个空的结果数组用于存储扁平化后的一维元素。在循环中，只要堆栈不为空，就从堆栈顶部取出当前元素。如果该元素是数组，则将其所有元素压入堆栈；如果不是数组，则直接将其添加到结果数组的开头。这个过程会不断深入到嵌套数组的最底层，然后再逐层返回，直至堆栈为空。

let arr = [1,2,[3,[4],[5,6,[7,8,[9]]]]]

function flattenWithDFS(arr) {
  const stack = [...arr] // 将原数组转换为堆栈
  const result = [] 

  while (stack.length > 0) { // 当堆栈中有待处理元素时
    const current = stack.pop() // 取出堆栈顶部的元素

    if (Array.isArray(current)) { 
      stack.push(...current) // 将其所有元素压入堆栈
    } else {
      result.unshift(current) // 否则将非数组元素添加到结果数组的开头
    }
  }

  return result 
}

console.log(flattenWithDFS(arr));  // [1,2,3,4,5,6,7,8,9]

优点：

递归思想简化实现：深度优先搜索天然适用于解决递归问题，此方法避免了显式递归调用，但仍保持了递归处理的思想。
无需额外空间复杂度：相比于广度优先搜索需要队列保存每一层级的数据，深度优先搜索仅需一个堆栈即可，对于内存资源有限的情况更为友好。

缺点：

遍历顺序：深度优先搜索可能导致元素在扁平化后的一维数组中的顺序与原始嵌套数组中的层级顺序不同。
栈溢出风险：当面对极深的嵌套数组时，由于使用堆栈进行递归模拟，可能会遇到JavaScript堆栈大小限制导致的栈溢出错误。

7. lodash库的_.flattenDeep()

lodash库提供了一个现成的方法_.flattenDeep()，可以处理任意深度的嵌套数组。

import _ from 'lodash'

let arr = [1,2,[3,[4],[5,6,[7,8,[9]]]]] 

const flattenedArr = _.flattenDeep(nestedArr)

console.log(flattenedArr)

优点：第三方库封装，功能强大且经过优化，适用于各种复杂场景。缺点：增加项目依赖，不适合仅需简单扁平化且关注性能与体积的应用场景。

以上就是七种常见的数组扁平化的方式了，掌握了这七种数组扁平化的方法，这类问题相信你回答起来也会得心应手。今天就聊到这，至于数组扁平化的应用场景本文并未介绍，当然这也是一个非常重要的知识点，不过本文主要是总结一些方法，对于应用场景感兴趣的掘友们可自行搜索哦。如果还有其他的数组扁平化方法，欢迎大佬在评论区补充哦。我也会一并更新到文章去。觉得文章有帮助可以给个小赞哦。♥(ˆ◡ˆԅ)

面试官：你知道几种数组扁平化的方法？