Skip to content

Latest commit

 

History

History
200 lines (159 loc) · 6.95 KB

2363.md

File metadata and controls

200 lines (159 loc) · 6.95 KB
title description keywords
2363. 合并相似的物品
LeetCode 2363. 合并相似的物品题解，Merge Similar Items，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
2363. 合并相似的物品
合并相似的物品
Merge Similar Items
解题思路
数组
哈希表
有序集合
排序

2363. 合并相似的物品

🟢 Easy  🔖  数组 哈希表 有序集合 排序  🔗 力扣 LeetCode

题目

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 value valuei.

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 合并两个二维数组 - 求和法 [✓] 数组 哈希表 双指针 🟢 🀄️ 🔗