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

LeetCode 350. 两个数组的交集 II

原题链接

难度:easy\color{Green}{easy}easy


题目描述

给你两个整数数组 nums1nums1nums1nums2nums2nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。

示例 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)

  1. 排序。
  2. 双指针遍历两个数组,如果 ·nums1 小,1的下标右移,nums2 小2右移。
  3. 如果相等,加入目标数组,直到退出循环。

复杂度分析

  • 时间复杂度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

(集合)

  1. 使用数据结构 unordered_multiset 存储 nums1 中的每个元素。
  2. 遍历数组 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

原题链接 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 给你两个整数数组 nums1nums1nums1 和 nums2nums2nums2 &#xff0c;请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数&#xff0c;应与元素在两个数组中都出现的次数一致&#xff08;如果出现…...

Python可以解码吗,解码打码是如何实现的

前言 咳咳&#xff0c;进来的铁汁都是抱着学习的心态进来看的吧&#xff0c;咱今天不讲解解码&#xff0c;咱来说说python如何来实现打码功能~ 这一个个进来的 都是标题党吧哈哈哈 有兴趣的可以继续看看哦 最近重温了一档综艺节目 至于叫什么 这里就不细说了 老是看着看着就…...

Jackson 序列化:Cannot deserialize value of type `java.time.LocalDateTime`

问题描述 使用 jackson 反序列化异常如下&#xff1a; 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_数据结构(一)_习题

数据结构&#xff08;一&#xff09;——练习题 学习完第三章-数据结构&#xff08;一&#xff09;之后&#xff0c;当然要做相应地练习啦~ 注&#xff1a;上述习题都可以在牛客进行测试。 例如&#xff0c;第2题链接&#xff1a;计算表达式_牛客题霸_牛客网 (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…...

网络爬虫简介

前言 没什么可以讲的所以就介绍爬虫吧 介绍 网络爬虫&#xff08;英语&#xff1a;web crawler&#xff09;&#xff0c;也叫网路蜘蛛&#xff08;spider&#xff09;&#xff0c;是一种用来自动浏览万维网的网络机器人。其目的一般为编纂网络索引。 网路搜索引擎等站点通过…...

通过4个月的自动化学习,现在我也拿到了25K的offer

毕业后的5年&#xff0c;是拉开职场差距的关键时期。有人通过这5年的努力&#xff0c;实现了大厂高薪&#xff0c;有人在这5年里得到贵人的赏识&#xff0c;实现了职级的快速拔升&#xff0c;还有人在这5年里逐渐掉队&#xff0c;成了职场里隐身一族&#xff0c;归于静默。 而…...

分库分表了解

数据切分根据其切分类型&#xff0c;可以分为两种方式&#xff1a;垂直&#xff08;纵向&#xff09;切分和水平&#xff08;横向&#xff09;切分一&#xff1a;垂直&#xff08;纵向&#xff09;切分【基于表或字段划分&#xff0c;表结构不同】1&#xff1a;垂直分库根据业务…...

docker中 gitlab 安装、配置和初始化

小笔记&#xff1a;gitlab配置文件 /etc/gitlab/gitlab.rb 配置项jcLee95 的CSDN博客&#xff1a;https://blog.csdn.net/qq_28550263?spm1001.2101.3001.5343 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/1…...

有哪些好用的C++Json库?

文章目录RapidJSONJSON for Modern CBoost.PropertyTreeJanssonPicoJSONC REST SDKnlohmann json&#xff08;ky用的这个&#xff09;jsoncpp&#xff08;cw用的这个&#xff09;RapidJSON RapidJSON是一个快速、高效的C JSON解析器和生成器&#xff0c;支持SAX和DOM两种解析模…...

Docker 快速上手学习入门教程

目录 1、docker 的基础概念 2、怎样打包和运行一个应用程序&#xff1f; 3、如何对 docker 中的应用程序进行修改&#xff1f; 4、如何对创建的镜像进行共享&#xff1f; 5、如何使用 volumes 名称对容器中的数据进行存储&#xff1f;// 数据挂载 6、另一种挂载方式&…...

深度学习笔记:误差反向传播(1)

1 计算图 计算图使用图&#xff08;由节点和边构成的图&#xff09;来表达算式。 如图&#xff0c;我们用节点代表运算符号&#xff0c;用边代表传入的参数&#xff0c;即可算出购买苹果和橘子的总价格。 2 计算图的局部计算 局部计算意味着每个节点只处理和其相关的运算&…...

锁相环(1)

PLL代表相位锁定环。顾名思义&#xff0c;如下图所示&#xff0c;PLL是一种具有反馈循环的电路&#xff0c;可将反馈信号的相/频率保持与参考输入信号的相/频率相同&#xff08;锁定&#xff09;。 如下图所示&#xff0c;如果参考输入和反馈输入之间存在相位差&#xff0c;则…...

2023金三银四跳槽必会Java核心知识点笔记整理

现在互联网大环境不好&#xff0c;互联网公司纷纷裁员并缩减 HC&#xff0c;更多程序员去竞争更少的就业岗位&#xff0c;整的 IT 行业越来越卷。身为 Java 程序员的我们就更不用说了&#xff0c;上班 8 小时需要做好本职工作&#xff0c;下班后还要不断提升技能、技术栈&#…...

二十四节气—雨水,好雨知时节,当春乃发生。

雨水&#xff0c;是二十四节气之第2个节气。 雨水节气不仅表明降雨的开始及雨量增多&#xff0c;而且表示气温的升高&#xff0c;意味着进入气象意义的春天。 雨水节是一个非常富有想象力和人情味的节气&#xff0c;在这一天&#xff0c;不管下不下雨都充满着一种雨意蒙蒙的诗…...

为什么要使用数据库?

随着互联网技术的高速发展&#xff0c;预计2020 年底全世界网民的数量将达到 50 亿。网民数量的增加带动了网上购物、微博&#xff0c;网络视频等产业的发展。那么&#xff0c;随之而来的就是庞大的网络数据量。 大量的数据正在不断产生&#xff0c;那么如何安全有效地存储、检…...

【原创】java+swing+mysql图书管理系统设计与实现

图书管理系统是一个比较常见的系统&#xff0c;今天我们主要介绍如何使用javaswiingmysql去开发一个cs架构的图书管理系统&#xff0c;方便学生进行图书借阅。 功能分析&#xff1a; 宿舍报修管理系统的使用角色&#xff0c;一般分为管理员和学生&#xff0c;管理员主要进行学…...

图论 —— 强连通分量

概念 连通图 无向图 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 引导定语从句&#xff0c;从句中缺宾语/表语&#xff0c;that可省略&#xff1b; 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…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...