2649. 嵌套数组生成器
2649. 嵌套数组生成器
题目
Given a multi-dimensional array of integers, return a generator object which yields integers in the same order as inorder traversal.
A multi-dimensional array is a recursive data structure that contains both integers and other multi-dimensional arrays.
inorder traversal iterates over each array from left to right, yielding any integers it encounters or applying inorder traversal to any arrays it encounters.
Example 1:
Input: arr = [[[6]],[1,3],[]]
Output: [6,1,3]
Explanation:
const generator = inorderTraversal(arr);
generator.next().value; // 6
generator.next().value; // 1
generator.next().value; // 3
generator.next().done; // true
Example 2:
Input: arr = []
Output: []
Explanation: There are no integers so the generator doesn't yield anything.
Constraints:
0 <= arr.flat().length <= 10^5
0 <= arr.flat()[i] <= 10^5
maxNestingDepth <= 10^5
Can you solve this without creating a new flattened version of the array?
题目大意
现给定一个整数的 多维数组 ,请你返回一个生成器对象,按照 中序遍历 的顺序逐个生成整数。
多维数组 是一个递归数据结构,包含整数和其他 多维数组 。
中序遍历 是从左到右遍历每个数组,在遇到任何整数时生成它,遇到任何数组时递归应用 中序遍历 。
示例 1:
输入: arr = [[[6]],[1,3],[]]
输出:[6,1,3]
解释:
const generator = inorderTraversal(arr);
generator.next().value; // 6
generator.next().value; // 1
generator.next().value; // 3
generator.next().done; // true
示例 2:
输入: arr = []
输出:[]
解释: 输入的多维数组没有任何参数,所以生成器不需要生成任何值。
提示:
0 <= arr.flat().length <= 10^5
0 <= arr.flat()[i] <= 10^5
maxNestingDepth <= 10^5
解题思路
要实现一个生成器,用于对一个整数的多维数组进行中序遍历,可以使用递归的方法。这个生成器会遍历数组中的每个元素,如果遇到整数,则生成该整数;如果遇到另一个数组,则递归地调用自身来处理该数组。
生成器函数:
inorderTraversal
是一个生成器函数,使用function*
定义。- 它接受一个参数
arr
,该参数是一个多维数组。
遍历数组:
- 使用
for...of
循环遍历数组中的每个元素。 Array.isArray(item)
用于检查当前元素是否是一个数组。
- 使用
递归生成:
- 如果当前元素是数组,则使用
yield*
关键字递归调用inorderTraversal(item)
,这会生成该子数组中的所有元素。 - 如果当前元素是整数,则使用
yield
直接生成该整数。
- 如果当前元素是数组,则使用
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组中所有整数的数量,因为每个整数都会被生成一次。 - 空间复杂度:
O(d)
,其中d
是递归的最大深度,这里主要用于保存函数调用栈。
代码
/**
* @param {Array} arr
* @return {Generator}
*/
var inorderTraversal = function* (arr) {
for (let item of arr) {
if (Array.isArray(item)) {
// 如果当前项是数组,则递归调用生成器
yield* inorderTraversal(item);
} else {
// 如果当前项是整数,直接生成该值
yield item;
}
}
};
/**
* const gen = inorderTraversal([1, [2, 3]]);
* gen.next().value; // 1
* gen.next().value; // 2
* gen.next().value; // 3
*/
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
2625 | 扁平化嵌套数组 | [✓] | ||
2648 | 生成斐波那契数列 | [✓] | ||
2650 | 设计可取消函数 | [✓] |