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

You are given two 2D integer arrays nums1 and nums2.

• nums1[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.
• nums2[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

• Only ids that appear in at least one of the two arrays should be included in the resulting array.
• Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be 0.

Return the resulting array. The returned array must be sorted in ascending order by id.

 

Example 1:

Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
Output: [[1,6],[2,3],[3,2],[4,6]]
Explanation: The resulting array contains the following:
- id = 1, the value of this id is 2 + 4 = 6.
- id = 2, the value of this id is 3.
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.

Example 2:

Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
Output: [[1,3],[2,4],[3,6],[4,3],[5,5]]
Explanation: There are no common ids, so we just include each id with its value in the resulting list.

 

Constraints:

• 1 <= nums1.length, nums2.length <= 200
• nums1[i].length == nums2[j].length == 2
• 1 <= idi, vali <= 1000
• Both arrays contain unique ids.
• Both arrays are in strictly ascending order by id.

/*
 * 题目思路：
 * 1. 使用 Java Stream API 来处理数组。
 * 2. 创建一个 HashMap 来存储 id 和 val 之和。
 * 3. 将 nums1 和 nums2 的元素流合并并收集到 HashMap 中。
 * 4. 将 HashMap 中的键值对提取并排序。
 * 5. 输出结果数组。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
        Map<Integer, Integer> map = Stream.concat(Arrays.stream(nums1), Arrays.stream(nums2))
            .collect(Collectors.toMap(
                num -> num[0],
                num -> num[1],
                Integer::sum
            ));
        int[][] result = new int[map.size()][2];
        int index = 0;
        for (int key : new TreeSet<>(map.keySet())) {
            result[index][0] = key;
            result[index][1] = map.get(key);
            index++;
        }
        return result;
    }
}

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

O(n + m + k log k)

O(n + m)