LeetCode 题解工作台
根据 ID 合并两个数组
现给定两个数组 arr1 和 arr2 ,返回一个新的数组 joinedArray 。两个输入数组中的每个对象都包含一个 id 字段。 joinedArray 是一个通过 id 将 arr1 和 arr2 连接而成的数组。 joinedArray 的长度应为唯一值 id 的长度。返回的数组应按 id…
0
题型
1
代码语言
0
相关题
当前训练重点
中等 · join·双·arrays·by·id·core·interview·pattern
答案摘要
function join(arr1: ArrayType[], arr2: ArrayType[]): ArrayType[] { const r = (acc: Obj, x: ArrayType): Obj => ((acc[x.id] = x), acc);
Interview AiBoxInterview AiBox 实时 AI 助手,陪你讲清 join·双·arrays·by·id·core·interview·pattern 题型思路
题目描述
现给定两个数组 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 中都有唯一的键值 id2 <= JSON.stringify(arr1).length <= 1062 <= JSON.stringify(arr2).length <= 106
解题思路
方法一
function join(arr1: ArrayType[], arr2: ArrayType[]): ArrayType[] {
const r = (acc: Obj, x: ArrayType): Obj => ((acc[x.id] = x), acc);
const d = arr1.reduce(r, {});
arr2.forEach(x => {
if (d[x.id]) {
Object.assign(d[x.id], x);
} else {
d[x.id] = x;
}
});
return Object.values(d);
}
type JSONValue = null | boolean | number | string | JSONValue[] | { [key: string]: JSONValue };
type ArrayType = { id: number } & Record<string, JSONValue>;
type Obj = Record<number, ArrayType>;
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n + m + k log k) where n and m are the lengths of arr1 and arr2, and k is the number of unique ids. Space complexity is O(k) to store the merged results in a map. |
| 空间 | ** Since we are creating a `joinedArray` to store the result, which can grow up to the size of `arr1` and `arr2` we can say that the space complexity is |
面试官常问的追问
外企场景- question_mark
Checking if you handle merging overlapping ids correctly.
- question_mark
Ensuring you sort the final array by id.
- question_mark
Evaluating if your solution handles unique and missing ids without errors.
常见陷阱
外企场景- error
Overwriting arr1 values incorrectly instead of using arr2 overrides.
- error
Failing to sort the resulting array by id.
- error
Not handling objects that exist in only one array.
进阶变体
外企场景- arrow_right_alt
Join arrays by id with nested object merging rules.
- arrow_right_alt
Handle arrays where arr2 may have additional fields not present in arr1.
- arrow_right_alt
Merge arrays where id fields are not initially sorted.