2675. 将对象数组转换为矩阵 🔒

🔴   🔗 力扣 LeetCode

题目

Write a function that converts an array of objects arr into a matrix m.

arr is an array of objects or arrays. Each item in the array can be deeply nested with child arrays and child objects. It can also contain numbers, strings, booleans, and null values.

The first row m should be the column names. If there is no nesting, the column names are the unique keys within the objects. If there is nesting, the column names are the respective paths in the object separated by ".".

Each of the remaining rows corresponds to an object in arr. Each value in the matrix corresponds to a value in an object. If a given object doesn't contain a value for a given column, the cell should contain an empty string "".

The columns in the matrix should be in lexographically ascending order.

Example 1:

Input:

arr = [

{"b": 1, "a": 2},

]

Output:

[

["a", "b"],

[2, 1],

[4, 3]

]

Explanation:

There are two unique column names in the two objects: "a" and "b".

"a" corresponds with [2, 4].

"b" coresponds with [1, 3].

Example 2:

Input:

arr = [

{"a": 1, "b": 2},

{"c": 3, "d": 4},

{}

]

Output:

[

["a", "b", "c", "d"],

[1, 2, "", ""],

["", "", 3, 4],

["", "", "", ""]

]

Explanation:

There are 4 unique column names: "a", "b", "c", "d".

The first object has values associated with "a" and "b".

The second object has values associated with "c" and "d".

The third object has no keys, so it is just a row of empty strings.

Example 3:

Input: arr = [

{"a": {"b": 1, "c": 2}},

{"a": {"b": 3, "d": 4}}

]

Output:

[

["a.b", "a.c", "a.d"],

[1, 2, ""],

[3, "", 4]

]

Explanation:

In this example, the objects are nested. The keys represent the full path to each value separated by periods.

There are three paths: "a.b", "a.c", "a.d".

Example 4:

Input:

arr = [

[{"a": null}],

[{"b": true}],

[{"c": "x"}]

]

Output:

[

["0.a", "0.b", "0.c"],

[null, "", ""],

["", true, ""],

["", "", "x"]

]

Explanation:

Arrays are also considered objects with their keys being their indices.

Each array has one element so the keys are "0.a", "0.b", and "0.c".

Example 5:

Input:

arr = [{}, {}, {}]

Output:

[[], [], [], []]

Explanation:

There are no keys so every row is an empty array.

Constraints:

• arr is a valid JSON array
• 1 <= arr.length <= 1000
• unique keys <= 1000

题目大意

编写一个函数，将对象数组 arr 转换为矩阵 m 。

arr 是一个由对象组成的数组或一个数组。数组中的每个项都可以包含深层嵌套的子数组和子对象。它还可以包含数字、字符串、布尔值和空值。

矩阵 m 的第一行应该是列名。如果没有嵌套，列名是对象中的唯一键。如果存在嵌套，列名是对象中相应路径，以点号 "." 分隔。

剩余的每一行对应 arr 中的一个对象。矩阵中的每个值对应对象中的一个值。如果给定对象在给定列中没有值，则应该包含空字符串 "" 。

矩阵中的列应按 字典序升序 排列。

提示：

• arr 是一个有效的 JSON 数组
• 1 <= arr.length <= 1000
• unique keys <= 1000

解题思路

1. 定义一个映射来存储键值：

   • 使用一个 Map（keyMap）来存储每个路径（键名）及其对应的值和行号

2. 深度优先搜索（DFS）函数：

   • 定义一个递归函数 dfs，用于遍历输入对象。
   • dfs 函数接收三个参数：当前对象、当前路径（prefix）和当前行号（row）。
   • 在遍历对象的键时，将当前键添加到路径前缀中（prefix），并检查该键的值：
     • 如果值是对象且不为 null，则递归调用 dfs。
     • 如果值是基本类型（如字符串、数字等），将完整路径（prefix）和对应的值及行号存入 keyMap。

3. 填充结果矩阵：

   • 创建一个矩阵 res，其行数为 arr.length + 1，列数为 keyMap.size，并初始化为全空字符串。
   • 第一行是经过排序的列名（即 keyMap 的所有键）。
   • 遍历 keyMap 的每个键，并根据记录的行号将对应的值填入矩阵。

4. 返回结果：

   • 最终返回构建好的矩阵 res。

复杂度分析

• 时间复杂度：O(n * m * d)，其中 n 为数组长度，假设每个对象中最多有 m 个键，且对象的深度为 d，需要遍历整个对象和所有深层嵌套。
• 空间复杂度：O(n * k)，其中 n 为数组长度，k 是唯一键路径的数量，哈希表 keyMap 的长度为 k，结果矩阵的大小为 (n + 1) * k，因此空间复杂度为 O(n * k)

代码

/**
 * @param {Array} arr
 * @return {String[][]}
 */
function jsonToMatrix(arr) {
	let keyMap = new Map();

	// 深度优先搜索函数
	const dfs = (obj, prefix, row) => {
		// 遍历对象的每个键
		for (let key of Object.keys(obj)) {
			prefix.push(key.toString());

			if (typeof obj[key] == 'object' && obj[key] !== null) {
				// 如果是对象且不为 null，递归调用 dfs
				dfs(obj[key], prefix, row);
			} else {
				// 生成完整的路径字符串
				const prefixStr = prefix.join('.');
				// 获取当前路径的值，并记录对应的行号
				const item = keyMap.get(prefixStr) || [];
				item.push({ value: obj[key], row });
				// 更新 keyMap
				keyMap.set(prefixStr, item);
			}

			// 回溯，移除最后一个键
			prefix.pop();
		}
	};

	// 遍历数组中的每个对象，调用 dfs
	arr.forEach((item, index) => dfs(item, [], index));

	// 初始化结果矩阵
	let res = new Array(arr.length + 1)
		.fill(0)
		.map(() => new Array(keyMap.size).fill(''));

	// 对路径字符串进行排序
	res[0] = Array.from(keyMap.keys()).sort();

	// 填充结果矩阵
	res[0].forEach((key, index) => {
		keyMap.get(key).forEach(({ value, row }) => {
			// 将对应的值填入矩阵
			res[row + 1][index] = value;
		});
	});

	return res; // 返回最终的矩阵
}

相关题目

题号	标题	题解	标签	难度	力扣
2628	完全相等的 JSON 字符串 🔒	[✓]		🟠	🀄️ 🔗
2633	将对象转换为 JSON 字符串 🔒	[✓]		🟠	🀄️ 🔗