LeetCode 题解工作台
合并相似的物品
给你两个二维整数数组 items1 和 items2 ，表示两个物品集合。每个数组 items 有以下特质： items[i] = [value i , weight i ] 其中 value i 表示第 i 件物品的 价值 ， weight i 表示第 i 件物品的 重量 。 items 中每件物…
4
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以用哈希表或数组 `cnt` 统计 `items1` 和 `items2` 中每个物品的总重量，然后从小到大遍历价值，将每个价值以及对应的总重量加入结果数组即可。 时间复杂度 $O(n + m)$，空间复杂度 $O(n + m)$。其中 和 分别是 `items1` 和 `items2` 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你两个二维整数数组 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]] 解释： 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 <= 1000items1[i].length == items2[i].length == 21 <= valuei, weighti <= 1000items1中每个valuei都是 唯一的 。items2中每个valuei都是 唯一的 。
解题思路
方法一：哈希表或数组
我们可以用哈希表或数组 cnt 统计 items1 和 items2 中每个物品的总重量，然后从小到大遍历价值，将每个价值以及对应的总重量加入结果数组即可。
时间复杂度 ，空间复杂度 。其中 和 分别是 items1 和 items2 的长度。
class Solution:
def mergeSimilarItems(
self, items1: List[List[int]], items2: List[List[int]]
) -> List[List[int]]:
cnt = Counter()
for v, w in chain(items1, items2):
cnt[v] += w
return sorted(cnt.items())
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate should demonstrate understanding of hash maps and their use for combining weighted values.
- question_mark
An optimal solution should focus on the use of array scanning and hash lookups for merging data efficiently.
- question_mark
Sorting the results after merging the values and their weights should be handled efficiently, using a fast sorting algorithm.
常见陷阱
外企场景- error
Not sorting the final result by value.
- error
Failing to handle edge cases, such as when one of the arrays is empty.
- error
Overcomplicating the solution by using inefficient data structures for merging.
进阶变体
外企场景- arrow_right_alt
What if the values in both arrays are guaranteed to be distinct?
- arrow_right_alt
What if the items are instead represented as objects with multiple attributes, including a value and weight?
- arrow_right_alt
What if the two arrays contain the same values but their weights are not guaranteed to be unique?