LeetCode 题解工作台
扁平化嵌套数组
请你编写一个函数，它接收一个 多维数组 arr 和它的深度 n ，并返回该数组的 扁平化 后的结果。 多维数组 是一种包含整数或其他 多维数组 的递归数据结构。 数组 扁平化 是对数组的一种操作，定义是将原数组部分或全部子数组删除，并替换为该子数组中的实际元素。只有当嵌套的数组深度小于 n 时，才应…
0
题型
1
代码语言
0
相关题
当前训练重点
中等 · flatten·deeply·nested·数组·core·interview·pattern
答案摘要
我们可以使用递归的方法，将多维数组扁平化。 在函数中，我们首先判断 是否小于等于 ，如果是，直接返回原数组。否则，我们遍历数组的每个元素 ，如果 是数组，我们递归调用函数，参数为 $(x, n - 1)$，将返回值添加到结果数组中；否则，将 添加到结果数组中。最后返回结果数组。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 flatten·deeply·nested·数组·core·interview·pattern 题型思路
题目描述
请你编写一个函数，它接收一个 多维数组 arr 和它的深度 n ，并返回该数组的 扁平化 后的结果。
多维数组 是一种包含整数或其他 多维数组 的递归数据结构。
数组 扁平化 是对数组的一种操作，定义是将原数组部分或全部子数组删除，并替换为该子数组中的实际元素。只有当嵌套的数组深度小于 n 时，才应该执行扁平化操作。第一层数组中元素的深度被认为是 0。
请在没有使用内置方法 Array.flat 的前提下解决这个问题。
示例 1：
输入 arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]] n = 0 输出 [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]] 解释 传递深度 n=0 的多维数组将始终得到原始数组。这是因为子数组(0)的最小可能的深度不小于 n = 0。因此，任何子数组都不应该被平面化。
示例 2：
输入 arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]] n = 1 输出 [1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15] 解释 以 4 、7 和 13 开头的子数组都被扁平化了，这是因为它们的深度为 0， 而 0 小于 1。然而 [9,10,11] 其深度为 1，所以未被扁平化。
示例 3：
输入 arr = [[1, 2, 3], [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]] n = 2 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 解释 所有子数组的最大深度都为 1。因此，它们都被扁平化了。
提示：
0 <= arr 的元素个数 <= 1050 <= arr 的子数组个数 <= 105maxDepth <= 1000-1000 <= each number <= 10000 <= n <= 1000
解题思路
方法一：递归
我们可以使用递归的方法，将多维数组扁平化。
在函数中，我们首先判断 是否小于等于 ，如果是，直接返回原数组。否则，我们遍历数组的每个元素 ，如果 是数组，我们递归调用函数，参数为 ，将返回值添加到结果数组中；否则，将 添加到结果数组中。最后返回结果数组。
时间复杂度 ，空间复杂度 。其中 是数组的元素个数。
type MultiDimensionalArray = (number | MultiDimensionalArray)[];
var flat = function (arr: MultiDimensionalArray, n: number): MultiDimensionalArray {
if (!n) {
return arr;
}
const ans: MultiDimensionalArray = [];
for (const x of arr) {
if (Array.isArray(x) && n) {
ans.push(...flat(x, n - 1));
} else {
ans.push(x);
}
}
return ans;
};
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for candidates who can implement recursion or iteration effectively to manage the depth of nested arrays.
- question_mark
Candidates should demonstrate an understanding of managing both space and time complexity when flattening arrays.
- question_mark
Watch for efficient solutions that avoid unnecessary recomputation or deep recursion, particularly for large arrays.
常见陷阱
外企场景- error
Overusing recursion can lead to excessive stack usage, especially when dealing with large arrays and deep nesting.
- error
Failing to properly track and limit depth can result in flattening elements that should remain nested, which breaks the problem constraints.
- error
Inefficient iteration methods may lead to excessive complexity, especially if they fail to optimize depth handling or flattening procedures.
进阶变体
外企场景- arrow_right_alt
Flatten the array only up to a certain depth, leaving subarrays deeper than the specified depth intact.
- arrow_right_alt
Ensure that the flattened version maintains the relative order of elements in all sub-arrays.
- arrow_right_alt
Support additional custom depth rules, where different arrays may have different flattening limits.