2722. 根据 ID 合并两个数组
2722. 根据 ID 合并两个数组
题目
Given two arrays arr1
and arr2
, return a new array joinedArray
. All the objects in each of the two inputs arrays will contain an id
field that has an integer value.
joinedArray
is an array formed by merging arr1
and arr2
based on their id
key. The length of joinedArray
should be the length of unique values of id
. The returned array should be sorted in ascending order based on the id
key.
If a given id
exists in one array but not the other, the single object with that id
should be included in the result array without modification.
If two objects share an id
, their properties should be merged into a single object:
- If a key only exists in one object, that single key-value pair should be included in the object.
- If a key is included in both objects, the value in the object from
arr2
should override the value fromarr1
.
Example 1:
Input:
arr1 = [
{"id": 1, "x": 1},
],
arr2 = [
]
Output:
[
{"id": 1, "x": 1},
{"id": 2, "x": 9},
]
Explanation: There are no duplicate ids so arr1 is simply concatenated with arr2.
Example 2:
Input:
arr1 = [
{"id": 1, "x": 2, "y": 3},
],
arr2 = [
{"id": 2, "x": 10, "y": 20},
]
Output:
[
{"id": 1, "x": 2, "y": 3},
{"id": 2, "x": 10, "y": 20},
]
Explanation: The two objects with id=1 and id=3 are included in the result array without modifiction. The two objects with id=2 are merged together. The keys from arr2 override the values in arr1.
Example 3:
Input:
arr1 = [
{"id": 1, "b": {"b": 94},"v": [4, 3], "y": 48}
]
arr2 = [
{"id": 1, "b": {"c": 84}, "v": [1, 3]}
]
Output: [
{"id": 1, "b": {"c": 84}, "v": [1, 3], "y": 48}
]
Explanation: The two objects with id=1 are merged together. For the keys "b" and "v" the values from arr2 are used. Since the key "y" only exists in arr1, that value is taken form arr1.
Constraints:
arr1
andarr2
are valid JSON arrays- Each object in
arr1
andarr2
has a unique integerid
key 2 <= JSON.stringify(arr1).length <= 10^6
2 <= JSON.stringify(arr2).length <= 10^6
题目大意
现给定两个数组 arr1
和 arr2
,返回一个新的数组 joinedArray
。两个输入数组中的每个对象都包含一个 id
字段。
joinedArray
是一个通过 id
将 arr1
和 arr2
连接而成的数组。joinedArray
的长度应为唯一值 id
的长度。返回的数组应按 id
升序 排序。
如果一个 id
存在于一个数组中但不存在于另一个数组中,则该对象应包含在结果数组中且不进行修改。
如果两个对象共享一个 id
,则它们的属性应进行合并:
- 如果一个键只存在于一个对象中,则该键值对应该包含在对象中。
- 如果一个键在两个对象中都包含,则
arr2
中的值应覆盖arr1
中的值。
提示:
arr1 和 arr2 都是有效的 JSON 数组
- 在
arr1
和arr2
中都有唯一的键值id
2 <= JSON.stringify(arr1).length <= 10^6
2 <= JSON.stringify(arr2).length <= 10^6
解题思路
创建一个字典,使用一个对象来存储第二个数组中以
id
为键的对象,以便快速查找。遍历第一个数组,对第一个数组中的每个对象进行遍历,根据当前对象的
id
在字典中查找对应的对象:- 如果找到匹配项,则合并两个对象;
- 如果没找到匹配项,则将当前对象加入字典中;
返回合并后的字典的
values
。
复杂度分析
- 时间复杂度:
O(m + n)
,其中m
和n
是两个数组的长度,首先遍历第二个数组构建字典,然后遍历第一个数组进行合并。 - 空间复杂度:
O(m + n)
,用于存储字典,最坏情况下要存储m + n
个键值对。
代码
/**
* @param {Array} arr1
* @param {Array} arr2
* @return {Array}
*/
var join = function (arr1, arr2) {
let dict = {};
arr2.forEach((item) => (dict[item.id] = item));
arr1.forEach((item) => {
if (dict[item.id]) {
dict[item.id] = { ...item, ...dict[item.id] };
} else {
dict[item.id] = item;
}
});
return Object.values(dict);
};