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

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
在这里插入图片描述

题目分析

题目描述

给定两个整数数组 nums1nums2,返回两个数组的交集。输出结果中的每个元素出现的次数,应与元素在两个数组中出现的次数一致。

算法分析

这个问题可以通过哈希表(无序映射)来解决。我们使用两个哈希表(p1p2)来存储两个数组中每个元素的出现次数。然后,我们遍历第一个哈希表,对于每个元素,如果它在第二个哈希表中也存在,则计算两个哈希表中该元素出现次数的最小值,并将其添加到结果数组中。

算法步骤

  1. 初始化两个哈希表 p1p2
  2. 遍历数组 nums1,将每个元素及其出现次数存储在 p1 中。
  3. 遍历数组 nums2,将每个元素及其出现次数存储在 p2 中。
  4. 初始化一个空向量 res 来存储结果。
  5. 遍历 p1,对于每个元素 k
    • 如果 p2 中包含 k,则找到 p2k 的位置。
    • 计算 p1k 的出现次数和 p2k 的出现次数的最小值。
    • k 添加到 res 中,次数为最小值。
  6. 返回 res

算法流程

开始
初始化无序映射 p1 和 p2
遍历 nums1
存储 nums1 元素在 p1
遍历 nums2
存储 nums2 元素在 p2
初始化空向量 res
遍历 p1
检查 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 函数。

注意事项

  • 确保在遍历数组时不要超出数组的边界。
  • 在处理映射时,确保不会覆盖任何元素。

相似题目

题目链接
两个数组的交集 IIhttps://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 &#xff0c;请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数&#xff0c;应与元素在两个数组中都出现的次数一致&#xff08;如果出现次数不一致&#xff0c;则考虑取较小值&#xff09;。可…...

基于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-笔记

上传图片木马文件后看到&#xff0c;检查的文件内容&#xff0c;包含<? 一句话木马提示 检查的文件格式 用如下图片木马&#xff0c;加上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 篇(二) - 卫星导航定位原理

专栏文章目录传送门&#xff1a;返回专栏目录 Hi, 我是你们的老朋友&#xff0c;主要专注于嵌入式软件开发&#xff0c;有兴趣不要忘记点击关注【码思途远】 文章目录 关注星号公众号&#xff0c;不容错过精彩 作者&#xff1a;HywelStar Hi, 我是你们的老朋友HywelStar, 根…...

怎样在 SQL 中对一个包含销售数据的表按照销售额进行降序排序?

在当今数字化商业的浪潮中&#xff0c;数据就是企业的宝贵资产。对于销售数据的有效管理和分析&#xff0c;能够为企业的决策提供关键的支持。而在 SQL 中&#xff0c;对销售数据按照销售额进行降序排序&#xff0c;是一项基础但极其重要的操作。 想象一下&#xff0c;您面前有…...

DIAdem 与 LabVIEW

DIAdem 和 LabVIEW 都是 NI (National Instruments) 公司开发的产品&#xff0c;尽管它们有不同的核心功能和用途&#xff0c;但它们在工程、测试和测量领域中常常一起使用&#xff0c;以形成一个完整的数据采集、分析、处理和报告生成的解决方案。 1. 功能和用途 LabVIEW (Lab…...

UE虚幻引擎可以云渲染吗?应用趋势与挑战了解

虚幻云渲染技术是基于虚幻引擎的云端渲染技术&#xff0c;将虚幻引擎的渲染计算任务通过云计算的方式进行处理和渲染、并将渲染结果传输到终端设备上进行展示。虚幻引擎云渲染技术在近年来得到了迅猛的发展&#xff0c;并在各个领域得到了广泛的应用&#xff0c;包括游戏、电影…...

实战分享:DefenderUI在企业环境中的部署与应用

前言 想象一下&#xff0c;你的电脑就像一座坚固的城堡&#xff0c;但城门却时常被一些不速之客窥探甚至企图入侵&#xff1b;Defender&#xff0c;作为城堡自带的守护者&#xff0c;实力自然不容小觑&#xff1b;但你是否觉得它有时候太过低调&#xff0c;有些隐藏技能还没完…...

中英双语介绍金融经济中的鹰派 (Hawkish)和鸽派 (Dovish)

中文版 在金融和经济政策中&#xff0c;“鹰派”和“鸽派”是两种对货币政策和经济管理有不同立场的群体。 鹰派 (Hawkish) 鹰派倾向于担心通货膨胀的风险&#xff0c;通常支持较高的利率和更紧的货币政策&#xff0c;以防止经济过热和控制物价上涨。具体特征包括&#xff1…...

Android 开发中常用的布局类型及其选择指南

在 Android 开发过程中,选择正确的布局类型对于构建高效、美观且响应式的用户界面至关重要。本文将介绍 Android 中几种最常用的布局类型,并对比它们的特点和适用场景,帮助开发者们做出明智的选择。 1. LinearLayout - 线性布局 特点: LinearLayout 是最基本的布局类型之一…...

短视频SDK解决方案,降低行业开发门槛

美摄科技匠心打造了一款集前沿技术与极致体验于一体的短视频SDK解决方案&#xff0c;它不仅重新定义了短视频创作的边界&#xff0c;更以行业标杆级的短视频特效&#xff0c;让每一帧画面都闪耀不凡光芒。 【技术赋能&#xff0c;创意无限】 美摄科技的短视频SDK&#xff0c;…...

【C++】String常见函数用法

一、string类对象的常见构造 我们可采取以下的方式进行构造&#xff0c;以下是常用的接口&#xff1a; //生成空字符串 string; //拷贝构造函数 string(const string& str); //用C-string来构造string类对象 string(const char* s); //string类对象中包含n个字符c strin…...

LeetCode49.字母异位词分组

题目大意 给你一个字符串数组&#xff0c;请你将字母异位词组合在一起。可以按任意顺序返回结果列表。 字母异位词是由重新排列源单词的所有字母得到的一个新单词。 思路分析 示例 1: 输入: strs ["eat", "tea", "tan", "ate", &…...

Nginx日志按天分割

需求、日志按照天的单位进行分割存储。 如果你直接百度&#xff0c;可能会搜到很多教你用各种脚本或是三方插件来按天分割的&#xff0c;这边我用nginx服务本身来分割日志。 方法一 通过使用 $time_iso8601 变量和 map 指令&#xff0c;实现了日志文件按天分割的功能。以下是…...

文本摘要简介

文本摘要是从一段长文本中提取出最重要的信息&#xff0c;并生成一个简短而有意义的摘要。这个过程可以分为两种主要方法&#xff1a; 抽取式摘要&#xff08;Extractive Summarization&#xff09;&#xff1a;从原文中直接提取出关键句子或段落&#xff0c;组成摘要…...

3.MySQL面试题之Redis 和 Mysql 如何保证数据一致性?

Redis 和 MySQL 数据一致性是分布式系统中的一个常见挑战。保证数据一致性通常涉及几种策略&#xff0c;我会详细解释这些策略并提供相应的代码示例。 先更新数据库&#xff0c;再更新缓存 这种方法先更新 MySQL&#xff0c;然后更新或删除 Redis 缓存。 Transactional publ…...

浅谈TCP协议、UDP协议

一、介绍说明 TCP&#xff08;传输控制协议&#xff09; 面向连接&#xff1a;TCP在数据传输之前必须建立连接。这通过一个称为三次握手的过程来完成&#xff0c;确保连接的两端都准备好进行数据传输。 可靠性&#xff1a;TCP提供可靠的数据传输&#xff0c;确保数据包正确无…...

SQL业务题: 从不订购的客户

1️⃣题目 Customers 表&#xff1a; ---------------------- | Column Name | Type | ---------------------- | id | int | | name | varchar | ---------------------- 在 SQL 中&#xff0c;id 是该表的主键。 该表的每一行都表示客户的 ID 和名…...

怎么直接在PDF上修改内容?随心编辑PDF内容

PDF(Portable Document Format)作为一种专用于阅读而非编辑的文档格式&#xff0c;其设计的核心目的是保持文档格式的一致性&#xff0c;确保文档在不同平台和设备上都能以相同的布局和格式呈现。然而&#xff0c;在实际工作和生活中&#xff0c;我们经常需要对PDF文档进行编辑…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...