Easy

题目描述

给你两个二维整数数组 items1 和 items2 ，表示两个物品集合。每个数组 items 有以下特性：

  • items[i] = [valuei, weighti] 其中 valuei 表示第 i 个物品的 值 ，weighti 表示第 i 个物品的 重量 。
  • items 中每个物品的值都是 唯一的 。

返回一个二维数组 ret，其中 ret[i] = [valuei, weighti]， weighti 是所有值为 valuei 物品的重量之和。

注意：ret 应该按值 升序 排序后返回。

示例 1：

输入：items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
输出：[[1,6],[3,9],[4,5]]
解释：
值为 1 的物品在 items1 中重量为 1 ，在 items2 中重量为 5 ，总重量为 1 + 5 = 6 。
值为 3 的物品在 items1 中重量为 8 ，在 items2 中重量为 1 ，总重量为 8 + 1 = 9 。
值为 4 的物品在 items1 中重量为 5 ，总重量为 5 。
因此，我们返回 [[1,6],[3,9],[4,5]] 。

示例 2：

输入：items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]
输出：[[1,4],[2,4],[3,4]]
解释：
值为 1 的物品在 items1 中重量为 1 ，在 items2 中重量为 3 ，总重量为 1 + 3 = 4 。
值为 2 的物品在 items1 中重量为 3 ，在 items2 中重量为 1 ，总重量为 3 + 1 = 4 。
值为 3 的物品在 items1 中重量为 2 ，在 items2 中重量为 2 ，总重量为 2 + 2 = 4 。
因此，我们返回 [[1,4],[2,4],[3,4]] 。

示例 3：

输入：items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]
输出：[[1,7],[2,4],[7,1]]
解释：
值为 1 的物品在 items1 中重量为 3 ，在 items2 中重量为 4 ，总重量为 3 + 4 = 7 。
值为 2 的物品在 items1 中重量为 2 ，在 items2 中重量为 2 ，总重量为 2 + 2 = 4 。
值为 7 的物品在 items2 中重量为 1 ，总重量为 1 。
因此，我们返回 [[1,7],[2,4],[7,1]] 。

提示：

  • 1 <= items1.length, items2.length <= 1000
  • items1[i].length == items2[i].length == 2
  • 1 <= valuei, weighti <= 1000
  • items1 中每个 valuei 都是 唯一的 。
  • items2 中每个 valuei 都是 唯一的 。

解题思路

这道题是一个典型的哈希表合并问题，需要将两个数组中相同值的物品重量进行累加。

解题思路：

  1. 使用哈希表统计重量：创建一个哈希表，以物品的值作为键，重量作为值。遍历两个数组，将每个物品的重量累加到对应值的键中。

  2. 排序输出：由于题目要求按照值的升序排列，我们需要将哈希表中的数据按键排序后输出。可以使用 map（自动排序）或先用 unordered_map 统计再排序。

  3. 具体步骤：

    • 遍历 items1 和 items2，将每个 [value, weight] 对的重量累加到哈希表中
    • 将哈希表转换为结果数组，由于需要按值升序排列，使用 map 可以自动保持顺序

推荐解法：使用 map 自动排序，代码简洁且效率较高。

代码实现

class Solution {
public:
    vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
        map<int, int> weightMap;
        
        // 统计 items1 中的重量
        for (auto& item : items1) {
            weightMap[item[0]] += item[1];
        }
        
        // 统计 items2 中的重量
        for (auto& item : items2) {
            weightMap[item[0]] += item[1];
        }
        
        // 构建结果
        vector<vector<int>> result;
        for (auto& pair : weightMap) {
            result.push_back({pair.first, pair.second});
        }
        
        return result;
    }
};

class Solution:
    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
        weight_map = {}
        
        # 统计 items1 中的重量
        for value, weight in items1:
            weight_map[value] = weight_map.get(value, 0) + weight
        
        # 统计 items2 中的重量
        for value, weight in items2:
            weight_map[value] = weight_map.get(value, 0) + weight
        
        # 按值升序排列并构建结果
        result = []
        for value in sorted(weight_map.keys()):
            result.append([value, weight_map[value]])
        
        return result

public class Solution {
    public IList<IList<int>> MergeSimilarItems(int[][] items1, int[][] items2) {
        var weightMap = new SortedDictionary<int, int>();
        
        // 统计 items1 中的重量
        foreach (var item in items1) {
            if (weightMap.ContainsKey(item[0])) {
                weightMap[item[0]] += item[1];
            } else {
                weightMap[item[0]] = item[1];
            }
        }
        
        // 统计 items2 中的重量
        foreach (var item in items2) {
            if (weightMap.ContainsKey(item[0])) {
                weightMap[item[0]] += item[1];
            } else {
                weightMap[item[0]] = item[1];
            }
        }
        
        // 构建结果
        var result = new List<IList<int>>();
        foreach (var pair in weightMap) {
            result.Add(new List<int> { pair.Key, pair.Value });
        }
        
        return result;
    }
}

var mergeSimilarItems = function(items1, items2) {
    const weightMap = new Map();
    
    // 统计 items1 中的重量
    for (const [value, weight] of items1) {
        weightMap.set(value, (weightMap.get(value) || 0) + weight);
    }
    
    // 统计 items2 中的重量
    for (const [value, weight] of items2) {
        weightMap.set(value, (weightMap.get(value) || 0) + weight);
    }
    
    // 按值升序排列并构建结果
    const result = [];
    const sortedKeys = Array.from(weightMap.keys()).sort((a, b) => a - b);
    
    for (const value of sortedKeys) {
        result.push([value, weightMap.get(value)]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度说明
时间复杂度O((n + m) log k)n、m分别为两个数组长度，k为不同值的数量，log k来自于map的插入操作
空间复杂度O(k)k为不同值的数量，用于存储哈希表

相关题目