跳到主要内容

数组扁平化 flat

问题​

手写实现数组扁平化（flat），支持指定展开深度。

答案​

数组扁平化是将多维数组转换为一维数组（或指定深度）的操作。

基础实现​

递归实现​

function flat<T>(arr: (T | T[])[], depth = 1): T[] {
  if (depth <= 0) {
    return arr.slice() as T[];
  }

  const result: T[] = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...flat(item, depth - 1));
    } else {
      result.push(item);
    }
  }

  return result;
}

// 测试
const nested = [1, [2, [3, [4, [5]]]]];
console.log(flat(nested, 1)); // [1, 2, [3, [4, [5]]]]
console.log(flat(nested, 2)); // [1, 2, 3, [4, [5]]]
console.log(flat(nested, Infinity)); // [1, 2, 3, 4, 5]

reduce 实现​

function flatReduce<T>(arr: (T | T[])[], depth = 1): T[] {
  return depth > 0
    ? arr.reduce<T[]>((acc, item) => {
        if (Array.isArray(item)) {
          acc.push(...flatReduce(item, depth - 1));
        } else {
          acc.push(item);
        }
        return acc;
      }, [])
    : (arr.slice() as T[]);
}

concat + apply（简洁版）​

// 只能展开一层
function flatOnce<T>(arr: (T | T[])[]): T[] {
  return ([] as T[]).concat(...arr);
}

// 或者用 apply
function flatOnceApply<T>(arr: (T | T[])[]): T[] {
  return Array.prototype.concat.apply([], arr) as T[];
}

// 测试
console.log(flatOnce([1, [2, 3], [4, [5]]])); // [1, 2, 3, 4, [5]]

完全展平（无限深度）​

递归方式​

function flatDeep<T>(arr: unknown[]): T[] {
  const result: T[] = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...flatDeep<T>(item));
    } else {
      result.push(item as T);
    }
  }

  return result;
}

// 简洁版
function flatDeepConcise<T>(arr: unknown[]): T[] {
  return arr.reduce<T[]>((acc, item) => {
    return acc.concat(Array.isArray(item) ? flatDeepConcise(item) : (item as T));
  }, []);
}

迭代方式（栈）​

function flatIterative<T>(arr: unknown[]): T[] {
  const stack = [...arr];
  const result: T[] = [];

  while (stack.length) {
    const item = stack.pop();

    if (Array.isArray(item)) {
      // 展开数组，保持顺序
      stack.push(...item);
    } else {
      result.push(item as T);
    }
  }

  // 因为是 pop，需要反转
  return result.reverse();
}

使用 flat 字符串转换（技巧）​

// 仅适用于简单类型数组
function flatByString(arr: number[]): number[] {
  return arr
    .toString()
    .split(',')
    .filter(Boolean)
    .map(Number);
}

// 测试
console.log(flatByString([1, [2, [3, [4]]]])); // [1, 2, 3, 4]

// 缺点：只能处理数字，无法处理字符串、对象等

Generator 实现​

function* flatGenerator<T>(arr: unknown[], depth = Infinity): Generator<T> {
  for (const item of arr) {
    if (Array.isArray(item) && depth > 0) {
      yield* flatGenerator<T>(item, depth - 1);
    } else {
      yield item as T;
    }
  }
}

// 使用
const arr = [1, [2, [3, [4]]]];
console.log([...flatGenerator<number>(arr)]); // [1, 2, 3, 4]
console.log([...flatGenerator<number>(arr, 1)]); // [1, 2, [3, [4]]]

扩展功能​

带过滤的扁平化​

function flatFilter<T>(
  arr: unknown[],
  predicate: (item: T) => boolean,
  depth = Infinity
): T[] {
  const result: T[] = [];

  function traverse(items: unknown[], d: number) {
    for (const item of items) {
      if (Array.isArray(item) && d > 0) {
        traverse(item, d - 1);
      } else if (predicate(item as T)) {
        result.push(item as T);
      }
    }
  }

  traverse(arr, depth);
  return result;
}

// 示例：扁平化并过滤偶数
const arr = [1, [2, [3, [4, [5]]]]];
console.log(flatFilter<number>(arr, (n) => n % 2 === 0)); // [2, 4]

带映射的扁平化（flatMap）​

function flatMap<T, U>(
  arr: T[],
  callback: (item: T, index: number, array: T[]) => U | U[]
): U[] {
  const result: U[] = [];

  arr.forEach((item, index) => {
    const mapped = callback(item, index, arr);
    if (Array.isArray(mapped)) {
      result.push(...mapped);
    } else {
      result.push(mapped);
    }
  });

  return result;
}

// 示例
const sentences = ['Hello World', 'Flat Map'];
console.log(flatMap(sentences, (s) => s.split(' ')));
// ['Hello', 'World', 'Flat', 'Map']

对象数组扁平化（展开嵌套属性）​

interface TreeNode {
  id: number;
  name: string;
  children?: TreeNode[];
}

function flattenTree(tree: TreeNode[]): Omit<TreeNode, 'children'>[] {
  const result: Omit<TreeNode, 'children'>[] = [];

  function traverse(nodes: TreeNode[]) {
    for (const node of nodes) {
      const { children, ...rest } = node;
      result.push(rest);
      if (children) {
        traverse(children);
      }
    }
  }

  traverse(tree);
  return result;
}

// 示例
const tree: TreeNode[] = [
  {
    id: 1,
    name: 'root',
    children: [
      { id: 2, name: 'child1' },
      {
        id: 3,
        name: 'child2',
        children: [{ id: 4, name: 'grandchild' }],
      },
    ],
  },
];

console.log(flattenTree(tree));
// [{ id: 1, name: 'root' }, { id: 2, name: 'child1' }, ...]

性能对比​

// 性能测试
const createNestedArray = (depth: number): unknown[] => {
  if (depth === 0) return [1];
  return [1, createNestedArray(depth - 1)];
};

const testArr = createNestedArray(100);

console.time('递归');
flat(testArr, Infinity);
console.timeEnd('递归');

console.time('迭代');
flatIterative(testArr);
console.timeEnd('迭代');

console.time('原生 flat');
(testArr as number[]).flat(Infinity);
console.timeEnd('原生 flat');
方法时间复杂度空间复杂度优点
递归O(n)O(n)O(d)O(d)，d 为深度代码简洁
迭代（栈）O(n)O(n)O(n)O(n)避免栈溢出
reduceO(n)O(n)O(d)O(d)函数式风格
GeneratorO(n)O(n)O(d)O(d)惰性求值

常见面试问题​

Q1: 实现 Array.prototype.flat​

答案：

declare global {
  interface Array<T> {
    myFlat(depth?: number): T[];
  }
}

Array.prototype.myFlat = function <T>(this: T[], depth = 1): T[] {
  const result: T[] = [];

  const flatten = (arr: unknown[], d: number) => {
    for (const item of arr) {
      if (Array.isArray(item) && d > 0) {
        flatten(item, d - 1);
      } else {
        result.push(item as T);
      }
    }
  };

  flatten(this, depth);
  return result;
};

// 测试
console.log([1, [2, [3]]].myFlat()); // [1, 2, [3]]
console.log([1, [2, [3]]].myFlat(2)); // [1, 2, 3]

Q2: flat 和 flatMap 的区别？​

答案：

const arr = [1, 2, 3];

// flat：仅扁平化
console.log([[1], [2], [3]].flat()); // [1, 2, 3]

// flatMap：先 map 再 flat(1)
console.log(arr.flatMap((x) => [x, x * 2])); // [1, 2, 2, 4, 3, 6]

// 等价于
console.log(arr.map((x) => [x, x * 2]).flat()); // [1, 2, 2, 4, 3, 6]

// flatMap 只能展开一层
console.log(arr.flatMap((x) => [[x]])); // [[1], [2], [3]]

Q3: 如何处理空位？​

答案：

// 原生 flat 会跳过空位
const sparse = [1, , [2, , 3]];
console.log(sparse.flat()); // [1, 2, 3]

// 手写实现
function flatSkipHoles<T>(arr: unknown[], depth = 1): T[] {
  const result: T[] = [];

  const flatten = (items: unknown[], d: number) => {
    for (let i = 0; i < items.length; i++) {
      // 跳过空位
      if (!(i in items)) continue;

      const item = items[i];
      if (Array.isArray(item) && d > 0) {
        flatten(item, d - 1);
      } else {
        result.push(item as T);
      }
    }
  };

  flatten(arr, depth);
  return result;
}

Q4: 递归深度过大怎么办？​

答案：

// 使用迭代方式避免栈溢出
function flatSafe<T>(arr: unknown[]): T[] {
  const stack: unknown[] = [...arr];
  const result: T[] = [];

  while (stack.length) {
    const item = stack.shift(); // 使用 shift 保持顺序

    if (Array.isArray(item)) {
      stack.unshift(...item);
    } else {
      result.push(item as T);
    }
  }

  return result;
}

// 或者使用尾递归优化（需要支持 TCO 的环境）
function flatTCO<T>(arr: unknown[], result: T[] = []): T[] {
  for (const item of arr) {
    if (Array.isArray(item)) {
      flatTCO(item, result);
    } else {
      result.push(item as T);
    }
  }
  return result;
}

Q5: 如何实现一个支持指定深度的 flat？Infinity 怎么处理？​

答案：

核心思路是通过 depth 参数控制递归展开的层数。每递归一层，depth 减 1，当 depth === 0 时停止展开，直接将元素原样放入结果数组。Infinity 作为特殊值，由于 Infinity - 1 仍然是 Infinity，因此可以实现无限展开，与 Array.prototype.flat(Infinity) 行为一致。

/**
 * 支持指定深度的 flat 实现
 * @param arr - 待扁平化的数组
 * @param depth - 展开深度，默认为 1，传 Infinity 表示完全展平
 */
function flat<T>(arr: (T | T[])[], depth: number = 1): T[] {
  // depth 为 0 时不再展开，直接返回浅拷贝
  if (depth <= 0) {
    return arr.slice() as T[];
  }

  const result: T[] = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      // depth - 1 控制递归深度；Infinity - 1 === Infinity，天然支持无限展开
      result.push(...flat(item, depth - 1));
    } else {
      result.push(item);
    }
  }

  return result;
}

// 测试：对标 Array.prototype.flat 的行为
const nested = [1, [2, [3, [4, [5]]]]];

// 默认展开 1 层
console.log(flat(nested));           // [1, 2, [3, [4, [5]]]]
console.log(nested.flat());          // [1, 2, [3, [4, [5]]]]（原生行为一致）

// 指定深度
console.log(flat(nested, 2));        // [1, 2, 3, [4, [5]]]
console.log(flat(nested, 3));        // [1, 2, 3, 4, [5]]

// depth 为 0，不展开
console.log(flat(nested, 0));        // [1, [2, [3, [4, [5]]]]]

// Infinity 完全展平
console.log(flat(nested, Infinity)); // [1, 2, 3, 4, 5]
console.log(nested.flat(Infinity));  // [1, 2, 3, 4, 5]（原生行为一致）
要点
  • depth 参数默认值为 1，与原生 Array.prototype.flat() 保持一致
  • Infinity - 1 === Infinity 是 JavaScript 的特性，无需对 Infinity 做特殊分支处理
  • depth <= 0 时返回数组的浅拷贝（arr.slice()），而非原数组引用，与原生行为一致

Q6: 除了递归，还有哪些方式实现数组扁平化？各有什么优缺点？​

答案：

主要有以下 5 种实现方式，适用场景和局限性各不相同：

1. toString + split（仅适合纯数字数组）

function flatByString(arr: number[]): number[] {
  return arr
    .toString()       // "1,2,3,4,5"
    .split(',')
    .filter(Boolean)
    .map(Number);
}

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

// 致命缺陷：无法处理字符串、对象、布尔值等
// flatByString(['a', ['b']]) → [NaN, NaN] ❌

2. reduce + concat（递归变体）

function flatReduce<T>(arr: (T | T[])[], depth: number = 1): T[] {
  return depth > 0
    ? arr.reduce<T[]>(
        (acc, item) =>
          acc.concat(
            Array.isArray(item) ? flatReduce(item, depth - 1) : item
          ),
        []
      )
    : (arr.slice() as T[]);
}

console.log(flatReduce([1, [2, [3]]], Infinity)); // [1, 2, 3]

3. 栈/队列迭代（避免栈溢出）

function flatStack<T>(arr: unknown[]): T[] {
  const stack = [...arr];
  const result: T[] = [];

  while (stack.length) {
    const item = stack.pop();
    if (Array.isArray(item)) {
      stack.push(...item); // 展开放回栈中
    } else {
      result.push(item as T);
    }
  }

  return result.reverse(); // pop 导致逆序，需要反转
}

console.log(flatStack<number>([1, [2, [3, [4]]]])); // [1, 2, 3, 4]

4. Generator 惰性求值

function* flatGen<T>(arr: unknown[], depth: number = Infinity): Generator<T> {
  for (const item of arr) {
    if (Array.isArray(item) && depth > 0) {
      yield* flatGen<T>(item, depth - 1);
    } else {
      yield item as T;
    }
  }
}

console.log([...flatGen<number>([1, [2, [3]]])]); // [1, 2, 3]

5. 展开运算符循环检测

function flatSpread<T>(arr: unknown[]): T[] {
  let result = [...arr];

  // 只要数组中还有嵌套数组，就继续展开一层
  while (result.some(Array.isArray)) {
    result = ([] as unknown[]).concat(...result);
  }

  return result as T[];
}

console.log(flatSpread<number>([1, [2, [3, [4]]]])); // [1, 2, 3, 4]

对比总结：

方式支持 depth支持所有类型时间复杂度空间复杂度优点缺点
toString + split不支持仅数字O(n)O(n)O(n)O(n)代码极简只能处理数字，实用性极低
reduce + concat支持支持O(n)O(n)O(d)O(d)函数式风格，支持 depth本质还是递归，深层嵌套会栈溢出
栈/队列迭代不支持（完全展平）支持O(n)O(n)O(n)O(n)避免栈溢出，适合极深嵌套不支持指定深度，需要 reverse
Generator支持支持O(n)O(n)O(d)O(d)惰性求值，支持 depth语法较新，性能略低于普通递归
展开运算符循环不支持（完全展平）支持O(n⋅d)O(n \cdot d)O(n)O(n)直观易懂每次循环创建新数组，性能最差
面试建议
  • 面试手写首选 递归实现（简洁、支持 depth），并能口述迭代方案作为优化
  • toString + split 方案只在面试中作为"你还知道哪些方式"的补充提及即可，要主动指出其局限性
  • 如果面试官追问"极深嵌套怎么办"，切换到栈迭代方案

相关链接​