合并相似的物品

难度: Easy

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

items[i] = [value_i, weight_i] 其中 value_i 表示第 i 件物品的价值，weight_i 表示第 i 件物品的重量。
items 中每件物品的价值都是 唯一的 。

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

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

示例 1：

输入：items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
输出：[[1,6],[3,9],[4,5]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 5 ，总重量为 1 + 5 = 6 。
value = 3 的物品再 items1 中 weight = 8 ，在 items2 中 weight = 1 ，总重量为 8 + 1 = 9 。
value = 4 的物品在 items1 中 weight = 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]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 3 ，总重量为 1 + 3 = 4 。
value = 2 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 1 ，总重量为 3 + 1 = 4 。
value = 3 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 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]]
解释：
value = 1 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 4 ，总重量为 3 + 4 = 7 。
value = 2 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
value = 7 的物品在 items2 中 weight = 1 ，总重量为 1 。
所以，我们返回 [[1,7],[2,4],[7,1]] 。

提示：

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

Submission

运行时间: 28 ms

内存: 16.8 MB

class Solution:
    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
        res = {}

        # 统计
        for v, w in items1:
            res[v] = w if v not in res else res[v] + w
        for v, w in items2:
            res[v] = w if v not in res else res[v] + w
        return [[v, w] for v, w in sorted(res.items())]

Explain

这个题解的思路是使用哈希表来记录每个物品的价值和累积的重量。首先遍历第一个物品集items1，将每个物品的价值作为键，其重量作为值加入到哈希表中。如果该价值已存在于哈希表中，则将新的重量加到已有的重量上。接着对第二个物品集items2重复相同的操作。最后，将哈希表中的键值对转换成题目要求的格式，并按价值升序排序输出。

时间复杂度: O(n1 + n2 + k log k)

空间复杂度: O(k)

class Solution:
    def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
        res = {}

        # 遍历第一个物品集合，累加相同价值的物品重量
        for v, w in items1:
            res[v] = w if v not in res else res[v] + w
        
        # 遍历第二个物品集合，累加相同价值的物品重量
        for v, w in items2:
            res[v] = w if v not in res else res[v] + w
        
        # 将结果字典转换为列表，并按价值升序排序返回
        return [[v, w] for v, w in sorted(res.items())]

Explore

在此题解中，通过使用哈希表（字典）的数据结构，可以有效处理相同价值的物品重量累加的问题。对于每个物品（价值，重量），如果价值已经在哈希表中存在，就将新的重量加到已有的重量上。这确保了即使物品价值相同但重量不同，它们的重量也会被准确地累加在一起。

在Python的字典（哈希表）中，哈希冲突是内部自动处理的。当两个不同的键具有相同的哈希值时，字典会使用链表或其他机制来解决冲突，确保每个键都能正确地映射到其对应的值。因此，在本题解中，使用的哈希表自动处理任何潜在的哈希冲突，不需要额外的处理逻辑。

尽管哈希表（字典）本身是无序的，但在将哈希表的内容转换为列表后，通过使用排序函数（如Python中的sorted()函数），可以按照任何需要的顺序（例如按价值升序）对列表进行排序。这保证了最终输出的列表是有序的，符合题目要求。

在这种处理方式中，每个新的价格值在首次出现时被添加到哈希表中，而不是被忽略或替换。这确保了所有出现的物品都被计数，因此不会影响最终结果中物品的总数。每个物品的价值都会在最终的列表中准确地表示出来，保证了数据的完整性和准确性。