河北 建设厅网站首页,帮网站做推广赚钱,江山网站设计,40岁了开始学室内设计来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你两个二维整数数组 items1 和 items2 #xff0c;表示两个物品集合。每个数组 items 有以下特质#xff1a;
items[i] [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 #xff0c;we…来源力扣LeetCode
描述
给你两个二维整数数组 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 都是 唯一的
方法哈希表
思路与算法
我们建立一个哈希表其键值表示物品价值其值为对应价值物品的重量之和。依次遍历 items1 和 items2 中的每一项物品同时更新哈希表。最后我们取出哈希表中的每一个键值对放入数组对数组按照 value 值排序即可。
有些语言可以在维护键值对的同时对键值对按照「键」进行排序比如 C 中的 std::map这样我们可以省略掉最后对数组的排序过程。
代码
class Solution {
public:vectorvectorint mergeSimilarItems(vectorvectorint items1, vectorvectorint items2) {mapint, int mp;for (auto v : items1) {mp[v[0]] v[1];}for (auto v : items2) {mp[v[0]] v[1];}vectorvectorint res;for (auto [k, v] : mp) {res.push_back({k, v});}return res;}
};执行用时8 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗16.4 MB, 在所有 C 提交中击败了56.10%的用户 复杂度分析 时间复杂度O((nm)log(nm))其中 n 是 items1 的长度m 是 items2 的长度。更新哈希表的时间复杂度为 O(nm)最后排序的时间复杂度为 (nm)log(nm)所以总的时间复杂度为 (nm)log(nm)。如果使用有序容器例如 C 中的 std::map其插入和查询的时间复杂度为 O(log(nm))故总体时间复杂度仍然是 O((nm)log(nm))。 空间复杂度O(nm)。哈希表所使用的空间为 O(nm)。如果使用有序容器例如 C 中的 std::map其内部实现为红黑树空间复杂度为 O(nm)。 authorLeetCode-Solution
