河南建设厅网站查证,阜宁做网站工作室,wordpress 禁用版本,西平县住房和城乡建设局网站给你两个二维整数数组 items1 和 items2 #xff0c;表示两个物品集合。每个数组 items 有以下特质#xff1a;
items[i] [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 #xff0c;weighti 表示第 i 件物品的 重量 。 items 中每件物品的价值都是 唯一的 。 请你…给你两个二维整数数组 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]] 。
1 items1.length, items2.length 1000 items1[i].length items2[i].length 2 1 valuei, weighti 1000 items1 中每个 valuei 都是 唯一的 。 items2 中每个 valuei 都是 唯一的 。
直接模拟即可
class Solution {
public:vectorvectorint mergeSimilarItems(vectorvectorint items1, vectorvectorint items2) {mapint, int mapAns;for (vectorint item : items1) {mapAns[item[0]] item[1];}for (vectorint item : items2) {mapAns[item[0]] item[1];}vectorvectorint ans;for (pairconst int, int item : mapAns) {vectorint oneAns {item.first, item.second};ans.push_back(oneAns);}return ans;}
};如果输入数组items1中有n个元素items2中有m个元素此算法时间复杂度为O(nm)lg(nm)空间复杂度为Onm。
