2722. 根据 ID 合并两个数组

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

现给定两个数组 arr1 和 arr2 ，返回一个新的数组 joinedArray 。两个输入数组中的每个对象都包含一个 id 字段。joinedArray 是一个通过 id 将 arr1 和 arr2 连接而成的数组。joinedArray 的长度应为唯一值 id 的长度。返回的数组应按 id 升序 排序。

如果一个 id 存在于一个数组中但不存在于另一个数组中，则该对象应包含在结果数组中且不进行修改。

如果两个对象共享一个 id ，则它们的属性应进行合并：

如果一个键只存在于一个对象中，则该键值对应该包含在对象中。
如果一个键在两个对象中都包含，则 arr2 中的值应覆盖 arr1 中的值。

示例 1：

输入：
arr1 = [
    {"id": 1, "x": 1},
    {"id": 2, "x": 9}
], 
arr2 = [
    {"id": 3, "x": 5}
]
输出：
[
    {"id": 1, "x": 1},
    {"id": 2, "x": 9},
    {"id": 3, "x": 5}
]
解释：没有共同的 id，因此将 arr1 与 arr2 简单地连接起来。

示例 2：

输入：
arr1 = [
    {"id": 1, "x": 2, "y": 3},
    {"id": 2, "x": 3, "y": 6}
], 
arr2 = [
    {"id": 2, "x": 10, "y": 20},
    {"id": 3, "x": 0, "y": 0}
]
输出：
[
    {"id": 1, "x": 2, "y": 3},
    {"id": 2, "x": 10, "y": 20},
    {"id": 3, "x": 0, "y": 0}
]
解释：id 为 1 和 id 为 3 的对象在结果数组中保持不变。id 为 2 的两个对象合并在一起。arr2 中的键覆盖 arr1 中的值。

示例 3：

输入：
arr1 = [
    {"id": 1, "b": {"b": 94},"v": [4, 3], "y": 48}
]
arr2 = [
    {"id": 1, "b": {"c": 84}, "v": [1, 3]}
]
输出： [
    {"id": 1, "b": {"c": 84}, "v": [1, 3], "y": 48}
]
解释：具有 id 为 1 的对象合并在一起。对于键 "b" 和 "v" ，使用 arr2 中的值。由于键 "y" 只存在于 arr1 中，因此取 arr1 的值。

提示：

• arr1 和 arr2 都是有效的 JSON 数组
• 在 arr1 和 arr2 中都有唯一的键值 id
• 2 <= JSON.stringify(arr1).length <= 106
• 2 <= JSON.stringify(arr2).length <= 106

解题思路

先将输入的两个数组按照元素的 id 属性进行排序，然后使用归并排序的方式将两个数组中的元素进行合并。具体来说，定义两个指针 ind1 和 ind2 分别指向两个数组的开头，然后依次比较两个指针所指向的元素的 id 属性。如果 arr1[ind1] 的 id 属性小于 arr2[ind2] 的 id 属性，则将 arr1[ind1] 加入结果数组，并将指针 ind1 向后移动一位；否则，将 arr2[ind2] 加入结果数组，并将指针 ind2 向后移动一位。如果两个指针所指向的元素的 id 属性相等，则将它们合并为一个新元素，并将指针 ind1 和 ind2 都向后移动一位。

最后，将剩余的数组元素加入结果数组，并返回合并后的结果。

AC代码

/**
 * @param {Array} arr1
 * @param {Array} arr2
 * @return {Array}
 */
var join = function(arr1, arr2) {
    arr1.sort((a,b)=>a.id - b.id);
    arr2.sort((a,b)=>a.id - b.id);
    const res = [];
    let ind1 = 0,ind2 = 0;
    while(ind1 < arr1.length && ind2 < arr2.length){
        if(arr1[ind1].id < arr2[ind2].id) res.push(arr1[ind1++]);
        else if(arr1[ind1].id > arr2[ind2].id) res.push(arr2[ind2++]);
        else res.push(Object.assign(arr1[ind1++],arr2[ind2++]));
    }
    while(ind1 < arr1.length) res.push(arr1[ind1++]);
    while(ind2 < arr2.length) res.push(arr2[ind2++]);
    return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。