跳至主要內容

2363. 合并相似的物品

2363. 合并相似的物品

🟢   🔖  数组 哈希表 有序集合 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given two 2D integer arrays, items1 and items2, representing two sets of items. Each array items has the following properties:

  • items[i] = [valuei, weighti] where valuei represents the value and weighti represents the weight of the ith item.
  • The value of each item in items is unique.

Return a 2D integer array ret where ret[i] = [valuei, weighti],with weighti being the sum of weights of all items with valuevaluei.

Note: ret should be returned in ascending order by value.

Example 1:

Input: items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]

Output: [[1,6],[3,9],[4,5]]

Explanation:

The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 5, total weight = 1 + 5 = 6.

The item with value = 3 occurs in items1 with weight = 8 and in items2 with weight = 1, total weight = 8 + 1 = 9.

The item with value = 4 occurs in items1 with weight = 5, total weight = 5.

Therefore, we return [[1,6],[3,9],[4,5]].

Example 2:

Input: items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]

Output: [[1,4],[2,4],[3,4]]

Explanation:

The item with value = 1 occurs in items1 with weight = 1 and in items2 with weight = 3, total weight = 1 + 3 = 4.

The item with value = 2 occurs in items1 with weight = 3 and in items2 with weight = 1, total weight = 3 + 1 = 4.

The item with value = 3 occurs in items1 with weight = 2 and in items2 with weight = 2, total weight = 2 + 2 = 4.

Therefore, we return [[1,4],[2,4],[3,4]].

Example 3:

Input: items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]

Output: [[1,7],[2,4],[7,1]]

Explanation: The item with value = 1 occurs in items1 with weight = 3 and in items2 with weight = 4, total weight = 3 + 4 = 7.

The item with value = 2 occurs in items1 with weight = 2 and in items2 with weight = 2, total weight = 2 + 2 = 4.

The item with value = 7 occurs in items2 with weight = 1, total weight = 1.

Therefore, we return [[1,7],[2,4],[7,1]].

Constraints:

  • 1 <= items1.length, items2.length <= 1000
  • items1[i].length == items2[i].length == 2
  • 1 <= valuei, weighti <= 1000
  • Each valuei in items1 is unique.
  • Each valuei in items2 is unique.

题目大意

给你两个二维整数数组 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 <= 1000
  • items1[i].length == items2[i].length == 2
  • 1 <= valuei, weighti <= 1000
  • items1 中每个 valuei 都是 唯一的 。
  • items2 中每个 valuei 都是 唯一的 。

解题思路

使用一个 Map 数据结构，可以方便地实现 value 到 weight 的映射，避免了复杂的查找。

  1. 将 items1 的所有条目初始化到 Map 中。
  2. 遍历 items2，将其中的条目合并到 Map 中（累加权重）。
  3. 将 Map 中的条目转化为数组并按 value 升序排序。

复杂度分析

  • 时间复杂度：O(n + m + k log k)

    • 初始化 Map：O(n)，其中 n 是 items1 的长度。
    • 遍历 items2：O(m)，其中 m 是 items2 的长度。
    • 排序：O(k log k)，其中 k 是合并后的不同 value 的数量。
    • 总体复杂度：O(n + m + k log k)。

  • 空间复杂度：O(k)，其中 k 是最终结果中不同 value 的数量，Map 存储合并后的条目。

代码

/**
 * @param {number[][]} items1
 * @param {number[][]} items2
 * @return {number[][]}
 */
var mergeSimilarItems = function (items1, items2) {
	// 初始化 Map，存储 items1 的条目
	let map = new Map(items1);

	// 遍历 items2，将权重累加到 Map 中
	for (let [value, weight] of items2) {
		map.set(value, (map.get(value) || 0) + weight);
	}

	// 将 Map 转化为数组并按 value 升序排序
	return [...map.entries()].sort((a, b) => a[0] - b[0]);
};

相关题目

题号标题题解标签难度力扣
2570合并两个二维数组 - 求和法[✓]数组 哈希表 双指针🟢🀄️open in new window 🔗open in new window