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

标签: 数组 哈希表 双指针

难度: Easy

给你两个 二维 整数数组 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 以严格递增顺序排列

Submission

运行时间: 23 ms

内存: 16.2 MB

from typing import List

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        merged_dict = {}  # 用于存储合并后的结果，键为id，值为对应的值
        i, j = 0, 0  # 双指针，分别指向nums1和nums2的当前位置
        
        # 遍历nums1和nums2，将元素添加到merged_dict中
        while i < len(nums1) and j < len(nums2):
            id1, val1 = nums1[i]
            id2, val2 = nums2[j]
            
            if id1 == id2:
                merged_dict[id1] = val1 + val2
                i += 1
                j += 1
            elif id1 < id2:
                merged_dict[id1] = merged_dict.get(id1, 0) + val1
                i += 1
            else:
                merged_dict[id2] = merged_dict.get(id2, 0) + val2
                j += 1
        
        # 处理剩余的nums1元素
        while i < len(nums1):
            id1, val1 = nums1[i]
            merged_dict[id1] = merged_dict.get(id1, 0) + val1
            i += 1
        
        # 处理剩余的nums2元素
        while j < len(nums2):
            id2, val2 = nums2[j]
            merged_dict[id2] = merged_dict.get(id2, 0) + val2
            j += 1
        
        # 将merged_dict转换为按id递增顺序排列的二维数组
        merged_list = sorted(merged_dict.items(), key=lambda x: x[0])
        
        # 返回最终结果
        return [[id, val] for id, val in merged_list]

Explain

本题的解题思路是使用哈希表（字典）来合并和累加两个二维数组中相同id的值。首先，我们初始化一个空字典`merged_dict`来存储每个id及其对应的累加值。使用双指针技术，分别遍历两个已按id递增排序的数组`nums1`和`nums2`。在遍历的过程中，比较两个数组当前元素的id，根据id的大小决定如何移动指针，并更新字典中的累加值。如果两个数组的当前id相同，则两个值相加后存入字典，并同时移动两个数组的指针。如果不相同，则将较小id的值加到字典中，并移动相应的指针。在完成双数组的遍历后，可能有一个数组还有剩余的元素未处理，继续遍历剩余数组并更新字典。最后，将字典转换为列表，并按id排序，以满足题目要求的输出格式。

时间复杂度: O(n + m + k log k)

空间复杂度: O(n + m)

from typing import List

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        merged_dict = {}  # 初始化字典，用于存储id和累加值
        i, j = 0, 0  # 初始化双指针分别指向两个数组

        # 使用双指针遍历两个数组
        while i < len(nums1) and j < len(nums2):
            id1, val1 = nums1[i]
            id2, val2 = nums2[j]

            if id1 == id2:
                merged_dict[id1] = val1 + val2  # 如果id相同，合并值
                i += 1
                j += 1
            elif id1 < id2:
                merged_dict[id1] = merged_dict.get(id1, 0) + val1  # 只更新nums1的当前项
                i += 1
            else:
                merged_dict[id2] = merged_dict.get(id2, 0) + val2  # 只更新nums2的当前项
                j += 1

        # 处理剩余的nums1元素
        while i < len(nums1):
            id1, val1 = nums1[i]
            merged_dict[id1] = merged_dict.get(id1, 0) + val1
            i += 1

        # 处理剩余的nums2元素
        while j < len(nums2):
            id2, val2 = nums2[j]
            merged_dict[id2] = merged_dict.get(id2, 0) + val2
            j += 1

        # 将字典结果转换为列表，并按id排序
        merged_list = sorted(merged_dict.items(), key=lambda x: x[0])

        # 构造最终结果格式
        return [[id, val] for id, val in merged_list]

Explore

在本题的上下文中，目标是合并两个数组并累加相同id的值。这种设计选择反映了一种假设，即相同id对应的值应该是累积的，例如在某些应用场景中，id可能代表同一实体或项目的不同记录，而累加则是为了得到一个综合的结果。如果选择取最大或最小值，那么会丢失原始数据中的信息量，无法反映出所有相关记录的总和，这可能不符合题目要求或实际的业务需求。

在这种情况下，继续将剩余数组中的元素加入字典是为了确保所有的数据都被充分利用。由于题目没有指定只处理两个数组中都有的id，因此单独存在于一个数组中的id也应该被计入最终结果。这样可以保证结果的完整性，确保每个数组中的所有id都得到了处理。

为了避免越界错误，解题代码中使用了两个指针分别指向两个数组的起始位置，并在循环条件中检查每个指针是否已经达到对应数组的长度。这意味着只要任何一个数组还有未处理的元素，循环就会继续执行。当一个数组中的元素被完全遍历后，另一个数组可能还有剩余的元素，这时通过单独的循环来继续处理剩余的元素，确保所有元素都被遍历，从而防止了越界错误。