当前位置: 首页 > news >正文

【2363. 合并相似的物品】

来源:力扣(LeetCode)

描述:

给你两个二维整数数组 items1items2 ,表示两个物品集合。每个数组 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 都是 唯一的

方法:哈希表

思路与算法

我们建立一个哈希表,其键值表示物品价值,其值为对应价值物品的重量之和。依次遍历 items1 和 items2 中的每一项物品,同时更新哈希表。最后,我们取出哈希表中的每一个键值对放入数组,对数组按照 value 值排序即可。

有些语言可以在维护键值对的同时,对键值对按照「键」进行排序,比如 C++ 中的 std::map,这样我们可以省略掉最后对数组的排序过程。

代码:

class Solution {
public:vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {map<int, int> mp;for (auto &v : items1) {mp[v[0]] += v[1];}for (auto &v : items2) {mp[v[0]] += v[1];}vector<vector<int>> 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((n+m)log(n+m)),其中 n 是 items1 的长度,m 是 items2 的长度。更新哈希表的时间复杂度为 O(n+m),最后排序的时间复杂度为 (n+m)log(n+m),所以总的时间复杂度为 (n+m)log(n+m)。如果使用有序容器(例如 C++ 中的 std::map),其插入和查询的时间复杂度为 O(log(n+m)),故总体时间复杂度仍然是 O((n+m)log(n+m))。
空间复杂度:O(n+m)。哈希表所使用的空间为 O(n+m)。如果使用有序容器(例如 C++ 中的 std::map),其内部实现为红黑树,空间复杂度为 O(n+m)。
author:LeetCode-Solution

相关文章:

【2363. 合并相似的物品】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你两个二维整数数组 items1 和 items2 &#xff0c;表示两个物品集合。每个数组 items 有以下特质&#xff1a; items[i] [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 &#xff0c;we…...

【C++提高编程】C++全栈体系(二十四)

C提高编程 第三章 STL - 常用容器 九、map/ multimap容器 1. map基本概念 简介&#xff1a; map中所有元素都是pairpair中第一个元素为key&#xff08;键值&#xff09;&#xff0c;起到索引作用&#xff0c;第二个元素为value&#xff08;实值&#xff09;所有元素都会根…...

c++11 标准模板(STL)(std::unordered_set)(十一)

定义于头文件 <unordered_set> template< class Key, class Hash std::hash<Key>, class KeyEqual std::equal_to<Key>, class Allocator std::allocator<Key> > class unordered_set;(1)(C11 起)namespace pmr { templ…...

AI/CV大厂笔试LeetCode高频考题之基础核心知识点

AI/CV互联网大厂笔试LeetCode高频考题之基础核心知识点算法复习1、二叉树的遍历2、回溯算法3、二分搜索4、滑动窗口算法题5、经典动态规划6、动态规划答疑篇6.1、总结一下如何找到动态规划的状态转移关系7、编辑距离8、戳气球问题9、最长公共子序列 Longest Common Subsequence…...

华为OD机试题,用 Java 解【静态扫描最优成本】问题

最近更新的博客 华为OD机试题,用 Java 解【停车场车辆统计】问题华为OD机试题,用 Java 解【字符串变换最小字符串】问题华为OD机试题,用 Java 解【计算最大乘积】问题华为OD机试题,用 Java 解【DNA 序列】问题华为OD机试 - 组成最大数(Java) | 机试题算法思路 【2023】使…...

常见无线技术方案介绍

无线技术 无线网络大体有两种&#xff1a;WAN&#xff08;广域网&#xff09;、PAN&#xff08;个人区域网&#xff09;。 对于LoRa&#xff0c;NB-IoT&#xff0c;2G / 3G / 4G等无线技术&#xff0c;通常传输距离超过1 km&#xff0c;因此它们主要用于广域网&#xff08;WA…...

收获满满的2022年

收到csdn官方的证书&#xff0c;感谢官方的认可&#xff01;...

react的生命周期

目录 一、初始化阶段 constructor() static getDerivedStateFromProps() componentWillMount() / UNSAFE_componentWillMount() render()&#xff1a; componentDidMount() 二、运行阶段 componentWillUpdate() / UNSAFE_componentWillUpdate() render() getSnapsh…...

scanpy 单细胞分析API接口使用案例

参考&#xff1a;https://zhuanlan.zhihu.com/p/537206999 https://scanpy.readthedocs.io/en/stable/api.html scanpy python包主要分四个模块&#xff1a; 1&#xff09;read 读写模块、 https://scanpy.readthedocs.io/en/stable/api.html#reading 2&#xff09;pp Prepr…...

【Vue3 第二十一章】Teleport组件传送

一、基本使用场景 有时我们可能会遇到这样的场景&#xff1a;一个组件模板的一部分在逻辑上从属于该组件&#xff0c;但从整个应用视图的角度来看&#xff0c;它在 DOM 中应该被渲染在整个 Vue 应用外部的其他地方。 这类场景最常见的例子就是全屏的模态框。理想情况下&#…...

在 Windows Subsystem for Linux (WSL2) 的 Ubuntu 系统上配置 Vulkan 开发环境

在 Windows Subsystem for Linux (WSL2) 的 Ubuntu 系统上配置 Vulkan 开发环境Vulkan Tutorial https://vulkan-tutorial.com/ Development environment - Linux https://vulkan-tutorial.com/Development_environment 1. Vulkan - Cross platform 3D Graphics https://www…...

放苹果HJ61

入门题目 把m个同样的苹果放在n个同样的盘子里&#xff0c;允许有的盘子空着不放&#xff0c;问共有多少种不同的分法&#xff1f;注意&#xff1a;如果有7个苹果和3个盘子&#xff0c;&#xff08;5&#xff0c;1&#xff0c;1&#xff09;和&#xff08;1&#xff0c;5&#…...

Windows下,OPC UA移植,open62541移植

OPC通信标准的核心是互通性 (Interoperability) 和标准化 (Standardization) 问题。传统的OPC技术在控制级别很好地解决了硬件设备间的互通性问题,在企业层面的通信标准化是同样需要的。OPC UA之前的访问规范都是基于微软的COM/DCOM技术, 这会给新增层面的通信带来不可根除的…...

【Tomcat与Servlet篇1】认识Tomcat与Maven

目录 一、什么是Tomcat 二、Tomcat的几个重要目录 conf文件​编辑 Server.xml logs文件 Webapps目录 三、如何使用Tomcat 但是&#xff0c;如果出现了点击之后进行闪退的情况&#xff0c;那又是怎么回事呢&#xff1f; 原因1&#xff1a;环境变量没有配置 原因2&#…...

C++类和对象:拷贝构造函数和运算符重载

目录 一. 拷贝构造函数 1.1 什么是拷贝构造函数 1.2 编译器默认生成的拷贝构造函数 1.3 拷贝构造函数特性总结 二. 运算符重载 2.1 运算符重载概述 2.2 比较运算符重载&#xff08;> > < <&#xff09; 2.2.1 >运算符的重载 2.2.2 运算符的重载 2.…...

【IntelliJ IDEA】idea plugins搜索不出来,如何找到插件的解决方案

一、背景描述安装好IDEA后&#xff0c;想下载一些插件来使用&#xff0c;因为IDEA非常方便的一点就是插件使用非常的方便&#xff0c;但是经常会发现进入到插件市场无法搜索到插件的情况&#xff0c;这个时候就有点烦人了。那么怎么解决这个问题呢&#xff1f;以下会把我能想到…...

移动端自动化测试(一)appium环境搭建

自动化测试有主要有两个分类&#xff0c;接口自动化和ui自动化&#xff0c;ui自动化呢又分移动端的和web端的&#xff0c;当然还有c/s架构的&#xff0c;这种桌面程序应用的自动化&#xff0c;使用QTP&#xff0c;只不过现在没人做了。 web自动化呢&#xff0c;现在基本上都是…...

5 逻辑回归及Python实现

1 主要思想 分类就是分割数据&#xff1a; 两个条件属性&#xff1a;直线&#xff1b;三个条件属性&#xff1a;平面&#xff1b;更多条件属性&#xff1a;超平面。 使用数据&#xff1a; 5.1,3.5,0 4.9,3,0 4.7,3.2,0 4.6,3.1,0 5,3.6,0 5.4,3.9,0 . . . 6.2,2.9,1 5.1,2.5…...

技术干货 | Modelica建模秘籍之状态变量

在很多领域都有“系统”这个概念&#xff0c;它描述的往往是一些复杂关系的总和。假如我们将系统看做一个黑箱&#xff0c;那么&#xff0c;在系统的作用下&#xff0c;外界的输入有时会产生令人意想不到的输出&#xff0c;“蝴蝶效应”就是其中的典型案例。图1 一只南美洲亚马…...

LeetCode 2574. 左右元素和的差值

给你一个下标从 0 开始的整数数组 nums &#xff0c;请你找出一个下标从 0 开始的整数数组 answer &#xff0c;其中&#xff1a; answer.length nums.length answer[i] |leftSum[i] - rightSum[i]| 其中&#xff1a; leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不…...

OpenClaw多任务调度:GLM-4.7-Flash并行处理文件与邮件

OpenClaw多任务调度&#xff1a;GLM-4.7-Flash并行处理文件与邮件 1. 为什么需要多任务调度 上周我需要同时处理两个紧急任务&#xff1a;整理三个月积累的会议录音文字稿&#xff0c;以及给二十多位合作伙伴发送定制化跟进邮件。手动操作需要至少6小时&#xff0c;而第二天早…...

RWKV7-1.5B-g1a参数详解教程:max_new_tokens/temperature/top_p调优实操手册

RWKV7-1.5B-g1a参数详解教程&#xff1a;max_new_tokens/temperature/top_p调优实操手册 1. 模型简介 rwkv7-1.5B-g1a 是基于新一代 RWKV-7 架构的多语言文本生成模型&#xff0c;特别适合中文场景下的基础问答、文案创作和简短总结任务。作为轻量级模型&#xff0c;它在保持良…...

VRCT:打破虚拟社交语言壁垒的创新解决方案

VRCT&#xff1a;打破虚拟社交语言壁垒的创新解决方案 【免费下载链接】VRCT VRCT(VRChat Chatbox Translator & Transcription) 项目地址: https://gitcode.com/gh_mirrors/vr/VRCT 在全球化的虚拟社交平台中&#xff0c;语言差异往往成为跨文化交流的最大障碍。当…...

Obsidian插件本地化全攻略:从英文界面到中文体验的完整实施路径

Obsidian插件本地化全攻略&#xff1a;从英文界面到中文体验的完整实施路径 【免费下载链接】obsidian-i18n 项目地址: https://gitcode.com/gh_mirrors/ob/obsidian-i18n 在全球化协作与知识管理的场景中&#xff0c;Obsidian插件的英文界面常成为用户高效使用的障碍。…...

突破Windows苹果设备连接限制:Apple-Mobile-Drivers-Installer的自动化驱动解决方案

突破Windows苹果设备连接限制&#xff1a;Apple-Mobile-Drivers-Installer的自动化驱动解决方案 【免费下载链接】Apple-Mobile-Drivers-Installer Powershell script to easily install Apple USB and Mobile Device Ethernet (USB Tethering) drivers on Windows! 项目地址…...

如何通过自动化工具高效获取阴阳师游戏资源?完整实践指南

如何通过自动化工具高效获取阴阳师游戏资源&#xff1f;完整实践指南 【免费下载链接】OnmyojiAutoScript Onmyoji Auto Script | 阴阳师脚本 项目地址: https://gitcode.com/gh_mirrors/on/OnmyojiAutoScript 阴阳师自动化工具是一款功能强大的智能辅助应用&#xff0c…...

粒子追踪模拟单透镜聚焦comsol ansys Fluent 二维三维模型 仿真模型,文献复现

粒子追踪模拟单透镜聚焦comsol ansys Fluent 二维三维模型 仿真模型&#xff0c;文献复现&#xff0c;热湿传递在实验室折腾粒子追踪仿真的时候&#xff0c;最让人上头的莫过于单透镜聚焦的场景搭建。COMSOL和ANSYS这对冤家各有各的脾气——前者把物理场耦合玩出花&#xff0…...

Cadence Virtuoso IC618版图验证全流程:解决PEX提参map error的详细步骤

Cadence Virtuoso IC618版图验证全流程&#xff1a;解决PEX提参map error的详细步骤 从IC514迁移到IC618的过程就像给老房子换新地基——表面上看功能相似&#xff0c;但底层架构的升级带来了全新的操作逻辑和隐藏的"陷阱"。最近三个月&#xff0c;我团队完成了7个项…...

【实战解析】PVE无显卡启动后网络失联:从硬件自检到系统绑定的完整排障指南

1. 无显卡启动的硬件准备与BIOS调试 当你准备在Proxmox VE&#xff08;PVE&#xff09;环境下实现无显卡启动时&#xff0c;首先要确保硬件层面支持这个特性。我遇到过不少用户直接拔掉显卡就期待系统能正常启动&#xff0c;结果发现连最基本的网络连接都失效了。这其实是个典型…...

矩阵按键的硬件设计与软件扫描实战

1. 矩阵按键的硬件设计要点 第一次接触矩阵按键时&#xff0c;我完全被它节省IO口的设计惊艳到了。想象一下&#xff0c;16个独立按键原本需要16个IO口&#xff0c;而4x4矩阵按键只需要8个IO口就能搞定。这种设计在资源受限的单片机项目中简直就是救命稻草。 硬件连接上有个容易…...