跳至主要內容

2649. 嵌套数组生成器


2649. 嵌套数组生成器open in new window

🟠   🔗 力扣open in new window LeetCodeopen in new window

题目

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

解题思路

要实现一个生成器,用于对一个整数的多维数组进行中序遍历,可以使用递归的方法。这个生成器会遍历数组中的每个元素,如果遇到整数,则生成该整数;如果遇到另一个数组,则递归地调用自身来处理该数组。

  1. 生成器函数

    • inorderTraversal 是一个生成器函数,使用 function* 定义。
    • 它接受一个参数 arr,该参数是一个多维数组。
  2. 遍历数组

    • 使用 for...of 循环遍历数组中的每个元素。
    • Array.isArray(item) 用于检查当前元素是否是一个数组。
  3. 递归生成

    • 如果当前元素是数组,则使用 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扁平化嵌套数组open in new window[✓]
2648生成斐波那契数列open in new window[✓]
2650设计可取消函数open in new window[✓]