LeetCode 350. 两个数组的交集 II
原题链接
难度:easy\color{Green}{easy}easy
题目描述
给你两个整数数组 nums1nums1nums1 和 nums2nums2nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
示例 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<=10001 <= nums1.length, nums2.length <= 10001<=nums1.length,nums2.length<=1000
- 0<=nums1[i],nums2[i]<=10000 <= nums1[i], nums2[i] <= 10000<=nums1[i],nums2[i]<=1000
** 进阶 :**
- 如果给定的数组已经排好序呢?你将如何优化你的算法?
- 如果 nums1nums1nums1 的大小比 nums2nums2nums2 小,哪种方法更优?
- 如果 nums2nums2nums2 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
算法
(排序双指针) O(n+m)O(n+m)O(n+m)
- 排序。
- 双指针遍历两个数组,如果 ·
nums1小,1的下标右移,nums2小2右移。 - 如果相等,加入目标数组,直到退出循环。
复杂度分析
-
时间复杂度:O(m+n)O(m + n)O(m+n)。
-
空间复杂度 : O(min(m+n))O(min(m + n))O(min(m+n))
C++ 代码
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());vector<int> res;int left = 0, right = 0;while (left < nums1.size() && right < nums2.size()) {if (nums1[left] < nums2[right])left ++;else if (nums1[left] == nums2[right]) {res.push_back(nums1[left]);left ++, right ++;} else {right ++;}}return res; }
};
算法2
(集合)
- 使用数据结构
unordered_multiset存储nums1中的每个元素。 - 遍历数组
nums2,如果在 集合中,把该值加入答案,并且在集合中删除该值。
复杂度分析
- 时间复杂度:O(n)O(n)O(n)。
C++ 代码
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_multiset<int> S;vector<int> res;for (int x : nums1) S.insert(x);for (int x : nums2)if (S.count(x)){res.push_back(x);S.erase(S.find(x));}return res;}
};
相关文章:
LeetCode 350. 两个数组的交集 II
原题链接 难度:easy\color{Green}{easy}easy 题目描述 给你两个整数数组 nums1nums1nums1 和 nums2nums2nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现…...
Python可以解码吗,解码打码是如何实现的
前言 咳咳,进来的铁汁都是抱着学习的心态进来看的吧,咱今天不讲解解码,咱来说说python如何来实现打码功能~ 这一个个进来的 都是标题党吧哈哈哈 有兴趣的可以继续看看哦 最近重温了一档综艺节目 至于叫什么 这里就不细说了 老是看着看着就…...
Jackson 序列化:Cannot deserialize value of type `java.time.LocalDateTime`
问题描述 使用 jackson 反序列化异常如下: Caused by: com.fasterxml.jackson.databind.exc.InvalidFormatException: Cannot deserialize value of type java.time.LocalDateTime from String “2023-02-13 19:43:01”: Failed to deserialize java.time.LocalDat…...
机试_3_数据结构(一)_习题
数据结构(一)——练习题 学习完第三章-数据结构(一)之后,当然要做相应地练习啦~ 注:上述习题都可以在牛客进行测试。 例如,第2题链接:计算表达式_牛客题霸_牛客网 (nowcoder.com)…...
《Hadoop篇》------HDFS与MapReduce
目录 一、HDFS角色职责总结 二、CheckPoint机制 三、Mapreduce序列化 四、Mapper 4.1、官方介绍 4.2、Split计算 4.3、Split和block对应关系 4.4、启发式算法 五、MapTask整体的流程 六、压缩算法 6.1、压缩算法适用场景 6.2、压缩算法选择 6.2.1、Gzip压缩 6.2…...
网络爬虫简介
前言 没什么可以讲的所以就介绍爬虫吧 介绍 网络爬虫(英语:web crawler),也叫网路蜘蛛(spider),是一种用来自动浏览万维网的网络机器人。其目的一般为编纂网络索引。 网路搜索引擎等站点通过…...
通过4个月的自动化学习,现在我也拿到了25K的offer
毕业后的5年,是拉开职场差距的关键时期。有人通过这5年的努力,实现了大厂高薪,有人在这5年里得到贵人的赏识,实现了职级的快速拔升,还有人在这5年里逐渐掉队,成了职场里隐身一族,归于静默。 而…...
分库分表了解
数据切分根据其切分类型,可以分为两种方式:垂直(纵向)切分和水平(横向)切分一:垂直(纵向)切分【基于表或字段划分,表结构不同】1:垂直分库根据业务…...
docker中 gitlab 安装、配置和初始化
小笔记:gitlab配置文件 /etc/gitlab/gitlab.rb 配置项jcLee95 的CSDN博客:https://blog.csdn.net/qq_28550263?spm1001.2101.3001.5343 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/details/1…...
有哪些好用的C++Json库?
文章目录RapidJSONJSON for Modern CBoost.PropertyTreeJanssonPicoJSONC REST SDKnlohmann json(ky用的这个)jsoncpp(cw用的这个)RapidJSON RapidJSON是一个快速、高效的C JSON解析器和生成器,支持SAX和DOM两种解析模…...
Docker 快速上手学习入门教程
目录 1、docker 的基础概念 2、怎样打包和运行一个应用程序? 3、如何对 docker 中的应用程序进行修改? 4、如何对创建的镜像进行共享? 5、如何使用 volumes 名称对容器中的数据进行存储?// 数据挂载 6、另一种挂载方式&…...
深度学习笔记:误差反向传播(1)
1 计算图 计算图使用图(由节点和边构成的图)来表达算式。 如图,我们用节点代表运算符号,用边代表传入的参数,即可算出购买苹果和橘子的总价格。 2 计算图的局部计算 局部计算意味着每个节点只处理和其相关的运算&…...
锁相环(1)
PLL代表相位锁定环。顾名思义,如下图所示,PLL是一种具有反馈循环的电路,可将反馈信号的相/频率保持与参考输入信号的相/频率相同(锁定)。 如下图所示,如果参考输入和反馈输入之间存在相位差,则…...
2023金三银四跳槽必会Java核心知识点笔记整理
现在互联网大环境不好,互联网公司纷纷裁员并缩减 HC,更多程序员去竞争更少的就业岗位,整的 IT 行业越来越卷。身为 Java 程序员的我们就更不用说了,上班 8 小时需要做好本职工作,下班后还要不断提升技能、技术栈&#…...
二十四节气—雨水,好雨知时节,当春乃发生。
雨水,是二十四节气之第2个节气。 雨水节气不仅表明降雨的开始及雨量增多,而且表示气温的升高,意味着进入气象意义的春天。 雨水节是一个非常富有想象力和人情味的节气,在这一天,不管下不下雨都充满着一种雨意蒙蒙的诗…...
为什么要使用数据库?
随着互联网技术的高速发展,预计2020 年底全世界网民的数量将达到 50 亿。网民数量的增加带动了网上购物、微博,网络视频等产业的发展。那么,随之而来的就是庞大的网络数据量。 大量的数据正在不断产生,那么如何安全有效地存储、检…...
【原创】java+swing+mysql图书管理系统设计与实现
图书管理系统是一个比较常见的系统,今天我们主要介绍如何使用javaswiingmysql去开发一个cs架构的图书管理系统,方便学生进行图书借阅。 功能分析: 宿舍报修管理系统的使用角色,一般分为管理员和学生,管理员主要进行学…...
图论 —— 强连通分量
概念 连通图 无向图 G G G 中,若对任意两点 V i , V j V_i, V_j V<...
计算机网络(二):物理层和链路层,通道复用,MAC地址,CSMA/CD协议,PPP点对点协议
文章目录一、物理层主机之间的通信方式通道复用技术常见的宽带接入技术二、链路层MAC地址和IP地址分别有什么作用为什么有了MAC地址之后还需要IP地址为什么有了IP地址还需要MAC地址以太网中的CSMA/CD协议数据链路层上的三个基本问题PPP协议一、物理层 主机之间的通信方式 单工…...
英语基础-定语从句的特殊用法及写作应用
1. 定语从句的引导词省略的情况 1. that 引导定语从句,从句中缺宾语/表语,that可省略; This is the book that he likes. I like the shirt that you gave me. We do not agree on the plan that you make. China is not the country th…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
Java多线程实现之Runnable接口深度解析
Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...
C++中vector类型的介绍和使用
文章目录 一、vector 类型的简介1.1 基本介绍1.2 常见用法示例1.3 常见成员函数简表 二、vector 数据的插入2.1 push_back() —— 在尾部插入一个元素2.2 emplace_back() —— 在尾部“就地”构造对象2.3 insert() —— 在任意位置插入一个或多个元素2.4 emplace() —— 在任意…...
Android多媒体——音/视频数据播放(十八)
在媒体数据完成解码并准备好之后,播放流程便进入了最终的呈现阶段。为了确保音视频内容能够顺利输出,系统需要首先对相应的播放设备进行初始化。只有在设备初始化成功后,才能真正开始音视频的同步渲染与播放。这一过程不仅影响播放的启动速度,也直接关系到播放的稳定性和用…...
