2570-合并两个二维数组 - 求和法

给你两个 二维 整数数组 nums1 和 nums2.

• nums1[i] = [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。
• nums2[i] = [idi, vali] 表示编号为 idi 的数字对应的值等于 vali 。

每个数组都包含 互不相同 的 id ，并按 id 以 递增 顺序排列。

请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：

• 只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。
• 每个 id 在结果数组中 只能出现一次 ，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ，则认为其对应的值等于 0 。

返回结果数组。返回的数组需要按 id 以递增顺序排列。

示例 1：

**输入：** nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
**输出：** [[1,6],[2,3],[3,2],[4,6]]
**解释：** 结果数组中包含以下元素：
- id = 1 ，对应的值等于 2 + 4 = 6 。
- id = 2 ，对应的值等于 3 。
- id = 3 ，对应的值等于 2 。
- id = 4 ，对应的值等于5 + 1 = 6 。

示例 2：

**输入：** nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
**输出：** [[1,3],[2,4],[3,6],[4,3],[5,5]]
**解释：** 不存在共同 id ，在结果数组中只需要包含每个 id 和其对应的值。

提示：

• 1 <= nums1.length, nums2.length <= 200
• nums1[i].length == nums2[j].length == 2
• 1 <= idi, vali <= 1000
• 数组中的 id 互不相同
• 数据均按 id 以严格递增顺序排列

下午两点【biIibiIi@灵茶山艾府】直播讲题，记得关注哦~

---

做法和归并排序是一样的。

[sol1-Python3]

class Solution:
    def mergeArrays(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
        ans = []
        i, n = 0, len(a)
        j, m = 0, len(b)
        while True:
            if i == n:
                ans.extend(b[j:])
                return ans
            if j == m:
                ans.extend(a[i:])
                return ans
            if a[i][0] < b[j][0]:
                ans.append(a[i])
                i += 1
            elif a[i][0] > b[j][0]:
                ans.append(b[j])
                j += 1
            else:
                a[i][1] += b[j][1]
                ans.append(a[i])
                i += 1
                j += 1

[sol1-Go]

func mergeArrays(a, b [][]int) (ans [][]int) {
	i, n := 0, len(a)
	j, m := 0, len(b)
	for {
		if i == n {
			return append(ans, b[j:]...)
		}
		if j == m {
			return append(ans, a[i:]...)
		}
		if a[i][0] < b[j][0] {
			ans = append(ans, a[i])
			i++
		} else if a[i][0] > b[j][0] {
			ans = append(ans, b[j])
			j++
		} else {
			a[i][1] += b[j][1]
			ans = append(ans, a[i])
			i++
			j++
		}
	}
}

复杂度分析

• 时间复杂度：O(n+m)，其中 n 为 nums}_1 的长度，m 为 nums}_2 的长度。
• 空间复杂度：O(1)。不计入返回值，仅用到若干额外变量。