跳至主要內容

2722. 根据 ID 合并两个数组

2722. 根据 ID 合并两个数组

🟠   🔗 力扣open in new window LeetCodeopen in new window

题目

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 from arr1.

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 and arr2 are valid JSON arrays
  • Each object in arr1 and arr2 has a unique integer id 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

解题思路

  1. 创建一个字典，使用一个对象来存储第二个数组中以 id 为键的对象，以便快速查找。

  2. 遍历第一个数组，对第一个数组中的每个对象进行遍历，根据当前对象的 id 在字典中查找对应的对象：

    • 如果找到匹配项，则合并两个对象；
    • 如果没找到匹配项，则将当前对象加入字典中；

  3. 返回合并后的字典的 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);
};