2675. Array of Objects to Matrix
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 colums in the matrix should be in lexographically ascending order.
Example 1:
Input:
arr = [
{“b”: 1, “a”: 2},
{“b”: 3, “a”: 4}
]
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.文章来源:https://www.toymoban.com/news/detail-455961.html
Constraints:
- 1 <= arr.length <= 1000
- unique keys <= 1000
From: LeetCode
Link: 2675. Array of Objects to Matrix
文章来源地址https://www.toymoban.com/news/detail-455961.html
Solution:
Ideas:
The JavaScript function jsonToMatrix() aims to convert an array of JavaScript objects (possibly nested) into a 2-dimensional matrix. It uses depth-first search (DFS) to traverse the nested objects, creating a unique set of keys and a map for each object in the input array.
Here’s the step-by-step idea behind this function:
1. Initialize empty maps and key set: For each object in the input array, an empty map is created. These maps will store keys and corresponding values for each object. An empty set is also created to store unique keys.
2. Iterative DFS on each object: For each object in the array, an iterative DFS is performed. The DFS uses a stack to keep track of the current state. It starts with the entire object, pushes each key into the stack, and recursively pushes nested keys if a value is an object or array.
3. Populate maps and key set: In the DFS, each time it encounters a key-value pair, it adds the key to the current path (represented as curr.join(‘.’)), and if the value isn’t an object or array, it sets this path and corresponding value in the map of the current object (lookup.set(curr.join(‘.’), u[v])). It also adds this key to the set of unique keys (keys_set.add(k)).
4. Construct the matrix: After populating the maps and key set, it constructs the matrix. The first row is filled with the sorted unique keys. For each subsequent row corresponding to an object, it checks if the object has a value for each key (column) and adds it to the row, or adds an empty string if there’s no value.
In this way, the function transforms an array of possibly nested objects into a matrix, where each row corresponds to an object, each column corresponds to a unique key, and each cell contains the value of the corresponding key for the corresponding object, or an empty string if the key doesn’t exist in the object. The keys are sorted in lexicographic order.
Note: The time complexity is O(l * mlogm + m * n) and the space complexity is O(l * m + m * n), where l is the maximum depth of the nested objects, m is the number of unique keys, and n is the number of objects in the array.
Code:
/**
* @param {Array} arr
* @return {Matrix}
*/
var jsonToMatrix = function(arr) {
let row = new Array(arr.length).fill(null).map(() => new Map());
let keys_set = new Set();
arr.forEach((x, i) => {
const iter_dfs = (u, lookup) => {
let stk = [[1, u, undefined]];
let curr = []
while (stk.length) {
const [step, u, v] = stk.pop();
if (step === 1) {
for (const v in u) {
stk.push([3, u, v]);
stk.push([2, u, v]);
}
} else if (step === 2) {
curr.push(v);
if (!(u[v] !== null && (typeof u[v] === 'object' || Array.isArray(u[v])))) {
lookup.set(curr.join('.'), u[v]);
} else {
stk.push([1, u[v], null])
}
} else if (step === 3) {
curr.pop();
}
}
}
iter_dfs(x, row[i]);
for (const [k, _] of row[i].entries()) {
keys_set.add(k);
}
});
let result = [Array.from(keys_set).sort()];
for (let i = 0; i < row.length; ++i) {
result.push([])
for (let j = 0; j < result[0].length; ++j) {
result[i+1].push(row[i].has(result[0][j]) ? row[i].get(result[0][j]) : '');
}
}
return result
};
到了这里,关于LeetCode //2675. Array of Objects to Matrix (Day 19 of LC JavaScript Challenge)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!