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，这个 id 对应的值为 2 + 4 = 6 。
- id = 2，这个 id 对应的值为 3 。
- id = 3，这个 id 对应的值为 2 。
- id = 4，这个 id 对应的值为 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 以严格递增顺序排列

解题思路

这道题有三种主要解法：

解法一：哈希表法 使用哈希表记录每个 id 对应的值之和。遍历两个数组，将相同 id 的值累加，最后按 id 排序输出。时间复杂度 O(n log n)。

解法二：双指针法（推荐） 由于两个数组都已按 id 递增排序，可以使用双指针同时遍历。比较当前指针指向的 id：

  • 如果 id 相同，将两个值相加
  • 如果不同，选择较小的 id，另一个数组的值视为 0

这种方法充分利用了有序性，时间复杂度 O(m + n)，空间复杂度 O(1)（不计结果数组）。

解法三：合并后去重 将两个数组合并，然后对相同 id 进行值的累加。实现相对复杂，效率不如双指针法。

双指针法是最优解，既简洁又高效，代码实现如下。

代码实现

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        vector<vector<int>> result;
        int i = 0, j = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i][0] == nums2[j][0]) {
                result.push_back({nums1[i][0], nums1[i][1] + nums2[j][1]});
                i++;
                j++;
            } else if (nums1[i][0] < nums2[j][0]) {
                result.push_back(nums1[i]);
                i++;
            } else {
                result.push_back(nums2[j]);
                j++;
            }
        }
        
        while (i < nums1.size()) {
            result.push_back(nums1[i++]);
        }
        
        while (j < nums2.size()) {
            result.push_back(nums2[j++]);
        }
        
        return result;
    }
};

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        result = []
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i][0] == nums2[j][0]:
                result.append([nums1[i][0], nums1[i][1] + nums2[j][1]])
                i += 1
                j += 1
            elif nums1[i][0] < nums2[j][0]:
                result.append(nums1[i])
                i += 1
            else:
                result.append(nums2[j])
                j += 1
        
        while i < len(nums1):
            result.append(nums1[i])
            i += 1
        
        while j < len(nums2):
            result.append(nums2[j])
            j += 1
        
        return result

public class Solution {
    public int[][] MergeArrays(int[][] nums1, int[][] nums2) {
        var result = new List<int[]>();
        int i = 0, j = 0;
        
        while (i < nums1.Length && j < nums2.Length) {
            if (nums1[i][0] == nums2[j][0]) {
                result.Add(new int[] {nums1[i][0], nums1[i][1] + nums2[j][1]});
                i++;
                j++;
            } else if (nums1[i][0] < nums2[j][0]) {
                result.Add(nums1[i]);
                i++;
            } else {
                result.Add(nums2[j]);
                j++;
            }
        }
        
        while (i < nums1.Length) {
            result.Add(nums1[i++]);
        }
        
        while (j < nums2.Length) {
            result.Add(nums2[j++]);
        }
        
        return result.ToArray();
    }
}

var mergeArrays = function(nums1, nums2) {
    const result = [];
    let i = 0, j = 0;
    
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度双指针法哈希表法
时间复杂度O(m + n)O(m + n + k log k)
空间复杂度O(1)O(k)

其中 m 和 n 分别是两个数组的长度，k 是不同 id 的总数。双指针法是最优解法。

相关题目