文章

手写：数组扁平化

深入探讨数组扁平化的多种实现方式：递归实现、reduce实现、栈实现、Generator实现

发表于
作者 独行的风
19 分钟阅读
手写：数组扁平化

一句话概括

数组扁平化是将多维数组转换为一维数组的过程，可通过递归、reduce、栈、Generator等多种方式实现，每种方式各有优劣。

背景

在实际开发中，我们经常遇到嵌套数组的处理需求：

1
2
3
4
5
6
7
8

// 后台返回的数据
const data = [
  { id: 1, children: [2, 3] },
  [4, 5, [6, 7]],
  [8, [9, 10]]
];

// 需要展平为：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

数组扁平化是前端面试的高频手写题，考察对递归、栈、Generator等概念的理解。

概念与定义

什么是数组扁平化

数组扁平化（Array Flatten）：将多维数组（嵌套数组）转换为一维数组的过程。

1
2
3
4
5

// 输入
const arr = [1, [2, [3, 4], 5], 6];

// 输出（扁平化后）
[1, 2, 3, 4, 5, 6]

原生flat方法

ES2019引入了 Array.prototype.flat() 方法：

1
2
3
4
5
6
7
8
9
10

const arr = [1, [2, [3, 4], 5], 6];

// 默认扁平化一层
arr.flat(); // [1, 2, [3, 4], 5, 6]

// 指定扁平化深度
arr.flat(2); // [1, 2, 3, 4, 5, 6]

// 完全扁平化（Infinity）
arr.flat(Infinity); // [1, 2, 3, 4, 5, 6]

核心知识点拆解

1. 递归实现（最直观）

基本递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function flatten(arr) {
  let result = [];
  
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      // 递归展开子数组
      result = result.concat(flatten(arr[i]));
    } else {
      result.push(arr[i]);
    }
  }
  
  return result;
}

// 测试
const arr = [1, [2, [3, 4], 5], 6];
flatten(arr); // [1, 2, 3, 4, 5, 6]

递归实现（使用forEach）

1
2
3
4
5
6
7
8
9
10
11
12
13

function flatten(arr) {
  let result = [];
  
  arr.forEach(item => {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item));
    } else {
      result.push(item);
    }
  });
  
  return result;
}

时间复杂度：O(n)（每个元素访问一次）
空间复杂度：O(n)（递归调用栈 + 结果数组）
优点：代码直观易懂
缺点：递归深度过大可能导致栈溢出

2. reduce实现（函数式风格）

1
2
3
4
5
6
7
8
9
10
11
12
13

function flatten(arr) {
  return arr.reduce((acc, curr) => {
    if (Array.isArray(curr)) {
      // 递归展开
      return acc.concat(flatten(curr));
    } else {
      return acc.concat(curr);
    }
  }, []);
}

// 测试
flatten([1, [2, [3, 4], 5], 6]); // [1, 2, 3, 4, 5, 6]

解析：

  • reduce 用于累积结果
  • 初始值：[]（空数组）
  • 如果当前元素是数组，递归展开后拼接
  • 如果当前元素不是数组，直接拼接

一行代码版本：

1

const flatten = arr => arr.reduce((acc, curr) => acc.concat(Array.isArray(curr) ? flatten(curr) : curr), []);

3. 栈实现（非递归，避免栈溢出）

原理

使用栈模拟递归过程，避免递归过深导致栈溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function flatten(arr) {
  const stack = [...arr]; // 将数组元素放入栈中
  const result = [];
  
  while (stack.length) {
    const next = stack.pop(); // 取出栈顶元素
    
    if (Array.isArray(next)) {
      // 如果是数组，将其元素展开后压入栈中
      stack.push(...next);
    } else {
      // 如果不是数组，加入结果数组
      result.push(next);
    }
  }
  
  // 反转结果（因为使用的是栈，顺序是反的）
  return result.reverse();
}

// 测试
flatten([1, [2, [3, 4], 5], 6]); // [1, 2, 3, 4, 5, 6]

优化：不使用reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function flatten(arr) {
  const stack = [...arr];
  const result = [];
  
  while (stack.length) {
    const next = stack.shift(); // 从前面取出（队列）
    
    if (Array.isArray(next)) {
      stack.unshift(...next); // 从前面插入
    } else {
      result.push(next);
    }
  }
  
  return result;
}

时间复杂度：O(n)
空间复杂度：O(n)
优点：避免递归栈溢出
缺点：代码不如递归直观

4. Generator实现（惰性求值）

原理

使用Generator函数，可以逐个返回扁平化后的元素，支持惰性求值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function* flatten(arr) {
  for (const item of arr) {
    if (Array.isArray(item)) {
      // 递归调用Generator
      yield* flatten(item);
    } else {
      yield item;
    }
  }
}

// 测试
const arr = [1, [2, [3, 4], 5], 6];
const result = [...flatten(arr)]; // [1, 2, 3, 4, 5, 6]

使用for…of遍历

1
2
3
4
5
6
7
8
9

function* flatten(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      yield* flatten(arr[i]);
    } else {
      yield arr[i];
    }
  }
}

优点：

  • 支持惰性求值（可以逐个处理元素）
  • 内存效率高（不需要一次性展开所有元素）
  • 代码简洁

应用场景：

1
2
3
4
5
6
7

// 处理大型嵌套数组，避免一次性占用大量内存
const bigArray = [/* 非常大的嵌套数组 */];

for (const item of flatten(bigArray)) {
  // 逐个处理元素
  processItem(item);
}

5. 扩展运算符实现（巧妙但有限制）

1
2
3
4
5
6
7
8
9
10
11

function flatten(arr) {
  // 只要数组中有数组，就继续展开
  while (arr.some(item => Array.isArray(item))) {
    arr = [].concat(...arr);
  }
  
  return arr;
}

// 测试
flatten([1, [2, [3, 4], 5], 6]); // [1, 2, 3, 4, 5, 6]

解析：

  • arr.some(item => Array.isArray(item))：检查是否还有数组元素
  • [].concat(...arr)：使用扩展运算符展开数组
  • 循环直到所有子数组都被展开

限制：

  • 只能展开一层（但循环使用可以展开多层）
  • 性能不如递归和栈实现

6. 指定扁平化深度（增强版）

实现可指定深度的扁平化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

function flatten(arr, depth = Infinity) {
  // 边界条件：深度为0或数组为空
  if (depth === 0 || !arr.length) {
    return arr;
  }
  
  return arr.reduce((acc, curr) => {
    if (Array.isArray(curr) && depth > 0) {
      // 递归展开，深度减1
      return acc.concat(flatten(curr, depth - 1));
    } else {
      return acc.concat(curr);
    }
  }, []);
}

// 测试
const arr = [1, [2, [3, [4, [5]]]]];

flatten(arr, 0); // [1, [2, [3, [4, [5]]]]]
flatten(arr, 1); // [1, 2, [3, [4, [5]]]]
flatten(arr, 2); // [1, 2, 3, [4, [5]]]
flatten(arr, 3); // [1, 2, 3, 4, [5]]]
flatten(arr, Infinity); // [1, 2, 3, 4, 5]

7. 原地扁平化（修改原数组）

原理

通过循环检查，如果发现有子数组，就将其展开插入到原位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function flattenInPlace(arr) {
  let i = 0;
  
  while (i < arr.length) {
    if (Array.isArray(arr[i])) {
      // 删除当前元素，插入展开的元素
      arr.splice(i, 1, ...arr[i]);
    } else {
      i++;
    }
  }
  
  return arr;
}

// 测试
const arr = [1, [2, [3, 4], 5], 6];
flattenInPlace(arr); // [1, 2, 3, 4, 5, 6]
console.log(arr); // [1, 2, 3, 4, 5, 6]（原数组被修改）

优点：节省内存（不需要创建新数组）
缺点：修改原数组（可能有副作用）

8. 性能对比

方法时间复杂度空间复杂度优点缺点
递归O(n)O(n)直观易懂可能栈溢出
reduceO(n)O(n)函数式风格可能栈溢出
栈O(n)O(n)避免栈溢出代码稍复杂
GeneratorO(n)O(n)惰性求值需要额外理解Generator
扩展运算符O(n²)O(n)代码简洁性能较差

实战案例

案例1：处理后台返回的嵌套数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 后台返回的数据
const response = {
  code: 200,
  data: [
    { id: 1, name: 'Alice', children: [2, 3] },
    [4, 5, [6, 7]],
    [8, [9, 10]]
  ]
};

// 提取所有ID
function extractIds(data) {
  // 扁平化数组
  const flattened = flatten(data);
  
  // 提取ID（可能是对象或数字）
  return flattened.map(item => {
    if (typeof item === 'object' && item !== null) {
      return item.id;
    }
    return item;
  });
}

console.log(extractIds(response.data)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

案例2：树形数据转一维数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// 树形数据
const treeData = [
  {
    id: 1,
    name: 'Node 1',
    children: [
      { id: 2, name: 'Node 1-1', children: [] },
      { id: 3, name: 'Node 1-2', children: [{ id: 4, name: 'Node 1-2-1' }] }
    ]
  },
  { id: 5, name: 'Node 2', children: [] }
];

// 提取所有节点（广度优先）
function flattenTree(nodes) {
  const result = [];
  const queue = [...nodes];
  
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    
    if (node.children && node.children.length) {
      queue.push(...node.children);
    }
  }
  
  return result;
}

console.log(flattenTree(treeData));
// [
//   { id: 1, name: 'Node 1', children: [...] },
//   { id: 5, name: 'Node 2', children: [] },
//   { id: 2, name: 'Node 1-1', children: [] },
//   { id: 3, name: 'Node 1-2', children: [...] },
//   { id: 4, name: 'Node 1-2-1' }
// ]

案例3：数组扁平化 + 去重 + 排序

1
2
3
4
5
6

const arr = [3, [1, 2, 2], [5, [3, 4, 4]], 1];

// 扁平化 → 去重 → 排序
const result = [...new Set(flatten(arr))].sort((a, b) => a - b);

console.log(result); // [1, 2, 3, 4, 5]

案例4：实现lodash的_.flattenDepth

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function flattenDepth(arr, depth = 1) {
  // 边界条件
  if (depth <= 0) return arr.slice();
  
  return arr.reduce((acc, curr) => {
    if (Array.isArray(curr) && depth > 0) {
      return acc.concat(flattenDepth(curr, depth - 1));
    } else {
      return acc.concat(curr);
    }
  }, []);
}

// 测试
const arr = [1, [2, [3, [4, [5]]]]];

flattenDepth(arr, 1); // [1, 2, [3, [4, [5]]]]
flattenDepth(arr, 2); // [1, 2, 3, [4, [5]]]
flattenDepth(arr, 3); // [1, 2, 3, 4, [5]]]

底层原理

1. 递归的调用栈

1
2
3
4
5

function flatten(arr) {
  console.log('递归深度:', new Error().stack.split('\n').length - 2);
  
  // ...递归逻辑
}

递归过深的问题：

  • 浏览器限制递归深度（Chrome约10000层）
  • 超过限制会抛出 RangeError: Maximum call stack size exceeded

解决方案：

  • 使用栈实现（非递归）
  • 使用尾递归优化（ES6，但浏览器支持有限）
  • 使用Generator实现

2. 尾递归优化（TCO）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 普通递归（无法优化）
function flatten(arr, result = []) {
  if (!arr.length) return result;
  
  const [first, ...rest] = arr;
  
  if (Array.isArray(first)) {
    return flatten([...first, ...rest], result); // 不是尾递归
  } else {
    return flatten(rest, [...result, first]); // 不是尾递归
  }
}

// 尾递归版本（ES6支持TCO）
function flatten(arr, result = []) {
  if (!arr.length) return result;
  
  const [first, ...rest] = arr;
  
  if (Array.isArray(first)) {
    return flatten([...first, ...rest], result); // 尾递归 ✅
  } else {
    return flatten(rest, result.concat(first)); // 尾递归 ✅
  }
}

注意：大部分浏览器（除了Safari）不支持TCO。

3. 内存占用分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 递归实现：每次递归调用都会创建新数组
function flattenRecursive(arr) {
  return arr.reduce((acc, curr) => {
    if (Array.isArray(curr)) {
      return acc.concat(flattenRecursive(curr)); // 创建新数组
    } else {
      return acc.concat(curr); // 创建新数组
    }
  }, []);
}

// 栈实现：复用同一个数组
function flattenStack(arr) {
  const stack = [...arr];
  const result = [];
  
  while (stack.length) {
    const next = stack.pop();
    
    if (Array.isArray(next)) {
      stack.push(...next); // 展开数组，不创建新数组
    } else {
      result.push(next);
    }
  }
  
  return result.reverse();
}

内存占用：栈实现 < 递归实现

高频面试题解析

1. 请手写一个数组扁平化函数

答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// 方法1：递归
function flatten(arr) {
  let result = [];
  
  for (const item of arr) {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item));
    } else {
      result.push(item);
    }
  }
  
  return result;
}

// 方法2：reduce
function flatten(arr) {
  return arr.reduce((acc, curr) => 
    acc.concat(Array.isArray(curr) ? flatten(curr) : curr), []);
}

// 方法3：栈
function flatten(arr) {
  const stack = [...arr];
  const result = [];
  
  while (stack.length) {
    const next = stack.pop();
    
    if (Array.isArray(next)) {
      stack.push(...next);
    } else {
      result.push(next);
    }
  }
  
  return result.reverse();
}

2. 数组扁平化的时间复杂度和空间复杂度是多少？

答：

  • 时间复杂度：O(n)，每个元素访问一次
  • 空间复杂度：O(n)，结果数组 + 递归栈/栈空间

3. 递归实现有什么问题？如何解决？

答：

  • 问题：递归深度过大可能导致栈溢出
  • 解决方案：
    1. 使用栈实现（非递归）
    2. 使用Generator实现
    3. 使用尾递归优化（浏览器支持有限）

4. 如何实现一个指定扁平化深度的函数？

答：

1
2
3
4
5
6
7
8
9
10
11

function flatten(arr, depth = Infinity) {
  if (depth === 0) return arr.slice();
  
  return arr.reduce((acc, curr) => {
    if (Array.isArray(curr) && depth > 0) {
      return acc.concat(flatten(curr, depth - 1));
    } else {
      return acc.concat(curr);
    }
  }, []);
}

5. Generator实现的优势是什么？

答：

  • 惰性求值：可以逐个处理元素，不需要一次性展开所有元素
  • 内存效率高：适合处理大型嵌套数组
  • 可暂停/继续：可以通过Generator控制执行流程

6. 如何判断一个数组是否已经被扁平化？

答：

1
2
3
4
5
6

function isFlattened(arr) {
  return !arr.some(item => Array.isArray(item));
}

isFlattened([1, 2, 3]); // true
isFlattened([1, [2, 3]]); // false

总结与扩展

核心要点总结

  1. 数组扁平化有多种实现方式：递归、reduce、栈、Generator等
  2. 递归实现最直观，但可能栈溢出
  3. 栈实现避免栈溢出，适合处理深层嵌套数组
  4. Generator实现支持惰性求值，内存效率高
  5. 原生flat方法最方便（ES2019+）

最佳实践

1
2
3
4
5
6
7
8

// ✅ 好的做法：根据场景选择合适的方法
// 1. 小规模数组：递归或reduce
// 2. 大规模或深层嵌套：栈或Generator
// 3. 现代浏览器：直接使用 arr.flat(Infinity)

// ❌ 避免：递归处理超大规模数组
const bigArray = /* 超大嵌套数组 */;
flattenRecursive(bigArray); // 可能栈溢出

扩展阅读

  1. ES2019 Array.prototype.flat()：MDN文档
  2. Generator函数：ES6 Generator
  3. 尾递归优化：ES6尾递归

相关技术

  • Array.prototype.flatMap()：先map再flat（深度1）
  • lodash.flatten()：lodash的扁平化函数
  • 递归与栈：数据结构与算法基础

本文详细讲解了数组扁平化的多种实现方式，以及它们的优缺点和适用场景。掌握这些内容，无论是面试还是实际开发都能游刃有余。

前端核心, JavaScript
本文由作者按照 CC BY 4.0 进行授权