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.

Constraints:

• 1 <= arr.length <= 1000
• unique keys <= 1000

From: LeetCode
Link: 2675. Array of Objects to Matrix
文章來(lái)源地址http://www.zghlxwxcb.cn/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
};

到了這里，關(guān)于LeetCode //2675. Array of Objects to Matrix (Day 19 of LC JavaScript Challenge)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！