算法 - 数组扁平化 (Flatten Array)

Posted on

1. 题目

实现一个函数，把可能嵌套多维的数组「摊平」成一维数组。前端面试手写题常客。

示例:

1
2
flatten([1, [2, [3, [4]], 5]])  ->  [1, 2, 3, 4, 5]
flatten([1, [2, 3], 4])         ->  [1, 2, 3, 4]

进阶要求：支持指定「扁平化深度」 flatten(arr, depth)，depth 表示要展开几层，Infinity 表示全部展开（对齐 Array.prototype.flat 的行为）。

2. 解题思路

嵌套结构 = 天然的递归场景。核心逻辑一句话：

遍历数组，遇到元素是数组就递归展开并把结果拼接，否则直接收集。

对于「限深度」版本，给递归加一个 depth 参数，每下钻一层 depth - 1，为 0 时不再展开直接返回当前层拷贝。

可以用多种流派展示功力：

  • reduce + 递归（最能体现思路，面试首推）。

  • 展开运算符 + 递归。

  • while + some + concat（检测是否还有数组，逐步拉平）。

  • toString 的副作用 trick（不推荐，会把 null 变空串）。

  • 生成器 function*（工程优雅，可迭代惰性展开）。

  • 时间复杂度：O(N)，N 为所有层级元素总数。

  • 空间复杂度：O(N) + 递归栈 O(最大深度)。

3. TypeScript 实现

3.1 基础版：reduce + 递归

1
2
3
4
5
6
7
8
9
type Nested = number | Nested[];

function flatten(arr: Nested[]): number[] {
    return arr.reduce<number[]>(
        (acc, cur) =>
            acc.concat(Array.isArray(cur) ? flatten(cur) : cur),
        []
    );
}

3.2 进阶版：支持 depth（对齐 Array.flat）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function flattenDepth(arr: Nested[], depth = 1): number[] {
    const res: number[] = [];

    const dfs = (input: Nested[], d: number) => {
        for (const item of input) {
            if (Array.isArray(item) && d > 0) {
                dfs(item, d - 1); // 下钻一层，深度预算 -1
            } else {
                res.push(item as number);
            }
        }
    };

    dfs(arr, depth);
    return res;
}

3.3 生成器版：可迭代、优雅

1
2
3
4
5
6
7
8
function* genFlat(arr: Nested[]): Generator<number> {
    for (const item of arr) {
        if (Array.isArray(item)) yield* genFlat(item);
        else yield item;
    }
}

const flattenGen = (arr: Nested[]): number[] => [...genFlat(arr)];
1
2
3
4
// 测试
console.log(flatten([1, [2, [3, [4]], 5]]));       // [1,2,3,4,5]
console.log(flattenDepth([1, [2, [3]]], 1));       // [1,2,[3]] -> [1,2,3 保留]
console.log(flattenDepth([1, [2, [3, [4]]], 5], Infinity)); // [1,2,3,4,5]

4. 面试延伸

  • flat vs flatMap：flatMap 只展开一层且能 map，性能略优于 map().flat()。
  • 对象/字符串边界：真实项目要判 Array.isArray，别用 typeof === 'object'，否则 null、字典对象会被误展开。
  • 保持类型：泛型进阶 type Flat<T> = ... 能在类型层面推导扁平结果，展示 TS 功底。
  • 一句话：能默写递归版是底线，能顺手写出限深度 + 生成器版就是加分项。

难度：简单 | 前端手写题 Top 10 | 递归基本功