2625. 扁平化嵌套数组

🟠   🔗 力扣 LeetCode

题目

Given a multi-dimensional array arr and a depth n, return a flattened version of that array.

A multi-dimensional array is a recursive data structure that contains integers or other multi-dimensional arrays.

A flattened array is a version of that array with some or all of the sub- arrays removed and replaced with the actual elements in that sub-array. This flattening operation should only be done if the current depth of nesting is less than n. The depth of the elements in the first array are considered to be 0.

Please solve it without the built-in Array.flat method.

Example 1:

Input

arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]

n = 0

Output

[1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]

Explanation

Passing a depth of n=0 will always result in the original array. This is because the smallest possible depth of a subarray (0) is not less than n=0. Thus, no subarray should be flattened.

Example 2:

Input

arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]

n = 1

Output

[1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15]

Explanation

The subarrays starting with 4, 7, and 13 are all flattened. This is because their depth of 0 is less than 1. However [9, 10, 11] remains unflattened because its depth is 1.

Example 3:

Input

arr = [[1, 2, 3], [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]

n = 2

Output

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Explanation

The maximum depth of any subarray is 1. Thus, all of them are flattened.

Constraints:

• 0 <= count of numbers in arr <= 10^5
• 0 <= count of subarrays in arr <= 10^5
• maxDepth <= 1000
• -1000 <= each number <= 1000
• 0 <= n <= 1000

题目大意

请你编写一个函数，它接收一个 多维数组 arr 和它的深度 n ，并返回该数组的 扁平化 后的结果。

多维数组 是一种包含整数或其他多维数组的递归数据结构。

数组 扁平化 是对数组的一种操作，定义是将原数组部分或全部子数组删除，并替换为该子数组中的实际元素。只有当嵌套的数组深度大于 n 时，才应该执行扁平化操作。第一层数组中元素的深度被认为是 0。

请在没有使用内置方法 Array.flat 的前提下解决这个问题。

提示：

• 0 <= arr 的元素个数 <= 10^5
• 0 <= arr 的子数组个数 <= 10^5
• maxDepth <= 1000
• -1000 <= each number <= 1000
• 0 <= n <= 1000

解题思路

1. 定义一个空数组 result 用于存储结果。
2. 定义内部递归函数 flattenArray，使用 forEach 遍历输入的嵌套数组。
3. 对于数组中的每个元素，：
   • 如果是其类型是数组且扁平化深度大于 0，递归调用 flattenArray 函数处理该数组。
   • 否则，直接将其添加到结果数组中。
4. 最后返回展平后的结果数组。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组中所有元素的总数，每个元素都需要被访问一次。
• 空间复杂度：O(n)，用于存储结果数组。

代码

/**
 * @param {Array} arr
 * @param {number} depth
 * @return {Array}
 */
var flat = function (arr, n) {
	let res = [];
	const flattenArray = (arr, n) => {
		arr.forEach((item) => {
			if (Array.isArray(item) && n > 0) {
				// 递归调用
				flattenArray(item, n - 1);
			} else {
				// 添加非数组元素
				res.push(item);
			}
		});
	};
	flattenArray(arr, n);
	return res;
};

相关题目

题号	标题	题解	标签	难度
2628	完全相等的 JSON 字符串 🔒	[✓]
2633	将对象转换为 JSON 字符串 🔒	[✓]
2649	嵌套数组生成器	[✓]