leetcode350. 两个数组的交集 II,哈希表
leetcode350. 两个数组的交集 II
给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
提示:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

题目分析
题目描述
给定两个整数数组 nums1 和 nums2,返回两个数组的交集。输出结果中的每个元素出现的次数,应与元素在两个数组中出现的次数一致。
算法分析
这个问题可以通过哈希表(无序映射)来解决。我们使用两个哈希表(p1 和 p2)来存储两个数组中每个元素的出现次数。然后,我们遍历第一个哈希表,对于每个元素,如果它在第二个哈希表中也存在,则计算两个哈希表中该元素出现次数的最小值,并将其添加到结果数组中。
算法步骤
- 初始化两个哈希表
p1和p2。 - 遍历数组
nums1,将每个元素及其出现次数存储在p1中。 - 遍历数组
nums2,将每个元素及其出现次数存储在p2中。 - 初始化一个空向量
res来存储结果。 - 遍历
p1,对于每个元素k:- 如果
p2中包含k,则找到p2中k的位置。 - 计算
p1中k的出现次数和p2中k的出现次数的最小值。 - 将
k添加到res中,次数为最小值。
- 如果
- 返回
res。
算法流程
具体代码
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> p1;unordered_map<int,int> p2;for(int i=0;i<nums1.size();i++){p1[nums1[i]]++;}for(int i=0;i<nums2.size();i++){p2[nums2[i]]++;}vector<int> res;for(auto k:p1){if(p2.count(k.first)){auto t=p2.find(k.first);int p1size=k.second;int p2size=t->second; int size=min(p1size,p2size);for(int j=0;j<size;j++){res.push_back(k.first);}}}return res;}
};
算法分析
复杂度分析
- 时间复杂度:O(m+n),其中 m 和 n 分别是两个数组的长度。我们只需要遍历两个数组一次。
- 空间复杂度:O(m+n),我们需要存储两个数组的元素及其出现次数,这取决于数组的长度。
易错点
- 在初始化两个无序映射时,确保正确地存储每个元素及其出现的次数。
- 在比较两个映射中的元素时,确保正确地使用
count函数。 - 在计算最小出现次数时,确保正确地使用
min函数。
注意事项
- 确保在遍历数组时不要超出数组的边界。
- 在处理映射时,确保不会覆盖任何元素。
相似题目
| 题目 | 链接 |
|---|---|
| 两个数组的交集 II | https://leetcode.com/problems/intersection-of-two-arrays-ii/ |
| 数组交集 | https://leetcode.com/problems/intersection-of-two-arrays/ |
| 查找重复的子树 | https://leetcode.com/problems/find-duplicate-subtrees/ |
| 两数之和 | https://leetcode.com/problems/two-sum/ |
相关文章:
leetcode350. 两个数组的交集 II,哈希表
leetcode350. 两个数组的交集 II 给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可…...
基于YOLOv8的缺陷检测任务模型训练
文章目录 一、引言二、环境说明三、缺陷检测任务模型训练详解3.1 PCB数据集3.1.1 数据集简介3.1.2 数据集下载3.1.3 构建yolo格式的数据集 3.2 基于ultralytics训练YOLOv83.2.1 安装依赖包3.2.2 ultralytics的训练规范说明3.2.3 创建训练配置文件3.2.4 下载预训练模型3.2.5 训练…...
【upload]-ini-[SUCTF 2019]CheckIn-笔记
上传图片木马文件后看到,检查的文件内容,包含<? 一句话木马提示 检查的文件格式 用如下图片木马,加上GIF89a绕过图片和<?检查 GIF89a <script languagephp>eval($_POST[cmd])</script> .user.ini实际上就是一个可以由用…...
uniapp条件编译使用教学(#ifdef、#ifndef)
#ifdef //仅在xxx平台使用#ifndef //除了在xxx平台使用#endif // 结束 标识平台APP-PLUSAPPMP微信小程序/支付宝小程序/百度小程序/头条小程序/QQ小程序MP-WEIXIN微信小程序MP-ALIPAY支付宝小程序MP-BAIDU百度小程序MP-TOUTIAO头条小程序MP-QQQQ小程序H5H5APP-PLUS-NVUEApp nv…...
NXP i.MX8系列平台开发讲解 - 4.1.2 GNSS 篇(二) - 卫星导航定位原理
专栏文章目录传送门:返回专栏目录 Hi, 我是你们的老朋友,主要专注于嵌入式软件开发,有兴趣不要忘记点击关注【码思途远】 文章目录 关注星号公众号,不容错过精彩 作者:HywelStar Hi, 我是你们的老朋友HywelStar, 根…...
怎样在 SQL 中对一个包含销售数据的表按照销售额进行降序排序?
在当今数字化商业的浪潮中,数据就是企业的宝贵资产。对于销售数据的有效管理和分析,能够为企业的决策提供关键的支持。而在 SQL 中,对销售数据按照销售额进行降序排序,是一项基础但极其重要的操作。 想象一下,您面前有…...
DIAdem 与 LabVIEW
DIAdem 和 LabVIEW 都是 NI (National Instruments) 公司开发的产品,尽管它们有不同的核心功能和用途,但它们在工程、测试和测量领域中常常一起使用,以形成一个完整的数据采集、分析、处理和报告生成的解决方案。 1. 功能和用途 LabVIEW (Lab…...
UE虚幻引擎可以云渲染吗?应用趋势与挑战了解
虚幻云渲染技术是基于虚幻引擎的云端渲染技术,将虚幻引擎的渲染计算任务通过云计算的方式进行处理和渲染、并将渲染结果传输到终端设备上进行展示。虚幻引擎云渲染技术在近年来得到了迅猛的发展,并在各个领域得到了广泛的应用,包括游戏、电影…...
实战分享:DefenderUI在企业环境中的部署与应用
前言 想象一下,你的电脑就像一座坚固的城堡,但城门却时常被一些不速之客窥探甚至企图入侵;Defender,作为城堡自带的守护者,实力自然不容小觑;但你是否觉得它有时候太过低调,有些隐藏技能还没完…...
中英双语介绍金融经济中的鹰派 (Hawkish)和鸽派 (Dovish)
中文版 在金融和经济政策中,“鹰派”和“鸽派”是两种对货币政策和经济管理有不同立场的群体。 鹰派 (Hawkish) 鹰派倾向于担心通货膨胀的风险,通常支持较高的利率和更紧的货币政策,以防止经济过热和控制物价上涨。具体特征包括࿱…...
Android 开发中常用的布局类型及其选择指南
在 Android 开发过程中,选择正确的布局类型对于构建高效、美观且响应式的用户界面至关重要。本文将介绍 Android 中几种最常用的布局类型,并对比它们的特点和适用场景,帮助开发者们做出明智的选择。 1. LinearLayout - 线性布局 特点: LinearLayout 是最基本的布局类型之一…...
短视频SDK解决方案,降低行业开发门槛
美摄科技匠心打造了一款集前沿技术与极致体验于一体的短视频SDK解决方案,它不仅重新定义了短视频创作的边界,更以行业标杆级的短视频特效,让每一帧画面都闪耀不凡光芒。 【技术赋能,创意无限】 美摄科技的短视频SDK,…...
【C++】String常见函数用法
一、string类对象的常见构造 我们可采取以下的方式进行构造,以下是常用的接口: //生成空字符串 string; //拷贝构造函数 string(const string& str); //用C-string来构造string类对象 string(const char* s); //string类对象中包含n个字符c strin…...
LeetCode49.字母异位词分组
题目大意 给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。 字母异位词是由重新排列源单词的所有字母得到的一个新单词。 思路分析 示例 1: 输入: strs ["eat", "tea", "tan", "ate", &…...
Nginx日志按天分割
需求、日志按照天的单位进行分割存储。 如果你直接百度,可能会搜到很多教你用各种脚本或是三方插件来按天分割的,这边我用nginx服务本身来分割日志。 方法一 通过使用 $time_iso8601 变量和 map 指令,实现了日志文件按天分割的功能。以下是…...
文本摘要简介
文本摘要是从一段长文本中提取出最重要的信息,并生成一个简短而有意义的摘要。这个过程可以分为两种主要方法: 抽取式摘要(Extractive Summarization):从原文中直接提取出关键句子或段落,组成摘要…...
3.MySQL面试题之Redis 和 Mysql 如何保证数据一致性?
Redis 和 MySQL 数据一致性是分布式系统中的一个常见挑战。保证数据一致性通常涉及几种策略,我会详细解释这些策略并提供相应的代码示例。 先更新数据库,再更新缓存 这种方法先更新 MySQL,然后更新或删除 Redis 缓存。 Transactional publ…...
浅谈TCP协议、UDP协议
一、介绍说明 TCP(传输控制协议) 面向连接:TCP在数据传输之前必须建立连接。这通过一个称为三次握手的过程来完成,确保连接的两端都准备好进行数据传输。 可靠性:TCP提供可靠的数据传输,确保数据包正确无…...
SQL业务题: 从不订购的客户
1️⃣题目 Customers 表: ---------------------- | Column Name | Type | ---------------------- | id | int | | name | varchar | ---------------------- 在 SQL 中,id 是该表的主键。 该表的每一行都表示客户的 ID 和名…...
怎么直接在PDF上修改内容?随心编辑PDF内容
PDF(Portable Document Format)作为一种专用于阅读而非编辑的文档格式,其设计的核心目的是保持文档格式的一致性,确保文档在不同平台和设备上都能以相同的布局和格式呈现。然而,在实际工作和生活中,我们经常需要对PDF文档进行编辑…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...
拟合问题处理
在机器学习中,核心任务通常围绕模型训练和性能提升展开,但你提到的 “优化训练数据解决过拟合” 和 “提升泛化性能解决欠拟合” 需要结合更准确的概念进行梳理。以下是对机器学习核心任务的系统复习和修正: 一、机器学习的核心任务框架 机…...
计算机系统结构复习-名词解释2
1.定向:在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方,那么就可以避免停顿。 2.多级存储层次:由若干个采用不同实现技术的存储…...
