两个数组的交集(力扣刷题)

        给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/intersection-of-two-arrays
 

说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

思路

        这道题目,主要要学会使用一种哈希数据结构:unordered_set,这个数据结构可以解决很多类似的问题。

        注意题目特意说明:输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的, 同时可以不考虑输出结果的顺序

        这道题用暴力的解法时间复杂度是O(n^2),那来看看使用哈希法进一步优化。

        但是要注意,使用数组来做哈希的题目,是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小,就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了,set ,关于set,C++ 给提供了如下三种可用的数据结构:

  • std::set
  • std::multiset
  • std::unordered_set

std::set和std::multiset底层实现都是红黑树,std::unordered_set的底层实现是哈希表, 使用unordered_set 读写效率是最高的,并不需要对数据进行排序,而且还不要让数据重复,所以选择unordered_set。        

思路如图所示:

 当然本题也有数组法,一样放在下面。

C++代码如下:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //set法
        
    //    unordered_set<int> result_set;
    //    unordered_set<int> nums_set(nums1.begin(),nums1.end());

    //    for(int num : nums2)
    //    {
    //        if(nums_set.find(num) != nums_set.end())
    //        {
    //            result_set.insert(num);
    //        }
    //    }

    //    return vector<int>(result_set.begin(),result_set.end());



       //数组法
       unordered_set<int> result_set;
       int hash[1005] = {0};
       for(int num : nums1)
       {
           hash[num] = 1;
       }

       for(int num : nums2)
       {
           if(hash[num] == 1)
           {
               result_set.insert(num);
           }
       }

       return vector<int>(result_set.begin(),result_set.end());
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/6064.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

人大女王金融硕士——站在一个更高的起点,拓宽自己的眼界

俗话说&#xff1a;“视野所及&#xff0c;心之所止”。做任何事情&#xff0c;最重要的是眼光。眼界不一样&#xff0c;就会有不一样的人生。站得更高才能看得更远&#xff0c;看得更远才能收获更多。人民大学与加拿大女王大学金融硕士项目为我们提供在职读研平台&#xff0c;…

Python机器学习:最大熵模型

信息论里&#xff0c;熵是可以度量随机变量的不确定性的&#xff0c;已经证明的&#xff1a;当随机变量呈均匀分布的时候&#xff0c;熵值最大&#xff0c;一个有序的系统有着较小的熵值&#xff0c;无序系统的熵值则较大。 机器学习里面&#xff0c;最大熵原理假设&#xff1…

【HAL库】HAL库STM32cubemx快速使用

文章目录整体框图一、基础工程1 新建工程2 配置RCC3 配置SYS4 工程设置5 生成代码6 keil设置下载&复位二、必备外设1 目录规范2 LED2 RTC3 USART4 KEY三、其他外设1 OLED&#xff08;模拟IIC、模拟SPI&#xff09;2 BH1750光强检测3 MQ2烟雾检测3 MQ4甲醛检测4 DHT11温湿度…

基于蓄电池进行调峰和频率调节研究【超线性增益的联合优化】(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。⛳座右铭&#…

第04章_运算符

第04章_运算符 &#x1f3e0;个人主页&#xff1a;shark-Gao &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是shark-Gao&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f389;目前状况&#xff1a;23届毕业生&#xff0c;目前在某公…

该不该放弃嵌入式,单片机这条路?

本文几乎浓缩了我从业10几年的精华&#xff0c;内容涵盖我转行、打工、创业的经历。 建议从头到尾不要错过一字一句&#xff0c;因为字里行间的经验之谈&#xff0c;或许能成为你人生重要转折点。 全文3700多字&#xff0c;写了6个多小时&#xff0c;如果你赶时间&#xff0c;建…

【17】核心易中期刊推荐——深度学习 | 遥感图像处理

🚀🚀🚀NEW!!!核心易中期刊推荐栏目来啦 ~ 📚🍀 核心期刊在国内的应用范围非常广,核心期刊发表论文是国内很多作者晋升的硬性要求,并且在国内属于顶尖论文发表,具有很高的学术价值。在中文核心目录体系中,权威代表有CSSCI、CSCD和北大核心。其中,中文期刊的数…

【学会这几个VSCode插件,让你的Python代码更优秀】

VSCode&#xff08;Visual Studio Code&#xff09;是由微软研发的一款免费、开源的跨平台文本&#xff08;代码&#xff09;编辑器&#xff0c;一般主要用于轻量级的编程代码工作&#xff0c;就非常适合Python&#xff0c;同时在前端开发方面也有举足轻重的地位。但如果想用于…

蓝桥杯集训·每日一题Week3

Trie AcWing 835. Trie字符串统计&#xff08;算法基础课&#xff09; 思路&#xff1a; Trie是一种高效地存储和查找字符串集合的数据结构,适用于字符串不太复杂的情况。其形状是一个以0为根节点的树&#xff0c;查询和插入的效率都比较高&#xff0c;有插入和查询两种操作。…

制造业的寒冬真的要来了吗?

制造业的寒冬真的要来了吗&#xff1f;其实当前&#xff0c;我国制造业发展水平是处于全球第三阵列&#xff0c;排名第四的&#xff1a; 但能处第三序列靠前&#xff0c;还是因为“规模发展”起了重要支撑——依靠规模拉动发展。所以如果从“质量效益”、“结构优化”、“持续发…

【AI探索】我问了ChatGPT几个终极问题

终于尝试了一把ChatGPT的强大之处&#xff0c;问了一下关心的几个问题&#xff1a; chatGPT现在在思考吗&#xff1f;有没有什么你感兴趣的问题&#xff1f; 你认为AI会对人类产生哪些方面的影响&#xff1f; 你对人类所涉及到的学科有了解吗&#xff1f;你认为在哪些方面与人类…

JetPack Compose之Modifier修饰符

前言 在Compose中&#xff0c;每一个组件都是带有Compose注解的函数&#xff0c;被称为Composable。Compose已经预置了很多的Compose UI组件&#xff0c;这些组件都是基于Material Design规范设计的&#xff0c;例如Button&#xff0c;TextField&#xff0c;TopAPPBar等。在布…

IOC、AOP、和javca面试题

一、 1、控制反转&#xff08;IOC&#xff09; 将创建管理对象的工作交给容器来做。在容器初始化&#xff08;或在某个时间节点&#xff09;通过反射机制创建好对象&#xff0c;在使用时直接从容器中获取。 控制反转&#xff1a;将对象的控制权反过来交给容器管理。 IOC实现…

既然有http 请求,为什么还要用rpc调用?

先弄明白什么是RPC。 RPC&#xff08;Remote Procedure Call&#xff09;—远程过程调用&#xff0c;它是一种通过网络从远程计算机程序上请求服务&#xff0c;而不需要了解底层网络技术的协议。RPC协议假定某些传输协议的存在&#xff0c;如TCP或UDP&#xff0c;为通信程序之…

【面试】Java并发编程面试题

文章目录基础知识为什么要使用并发编程多线程应用场景并发编程有什么缺点并发编程三个必要因素是什么&#xff1f;在 Java 程序中怎么保证多线程的运行安全&#xff1f;并行和并发有什么区别&#xff1f;什么是多线程多线程的好处多线程的劣势&#xff1a;线程和进程区别什么是…

基于java+ssm+vue病人跟踪治疗信息管理系统的搭建及源码

源码获取方式见文末 一.需求简介 病人治疗信息管理系统采用B/S模式&#xff0c;实现安全、快捷、高效的病人跟踪治疗信息管理。传统手工管理模式效率低下&#xff0c;已无法满足病人需求。 信息化时代的到来&#xff0c;使得开发病人跟踪治疗信息管理系统成为必然。 本系统采…

Linux 串口RS232/485/GPS 驱动实验(移植minicom)

目录Linux 下UART 驱动框架I.MX6U UART 驱动分析硬件原理图分析RS232 驱动编写移植minicomRS232 驱动测试RS232 连接设置minicom 设置RS232 收发测试RS485 测试RS485 连接设置RS485 收发测试GPS 测试GPS 连接设置GPS 数据接收测试串口是很常用的一个外设&#xff0c;在Linux 下…

python入门(一)conda的使用,创建修改删除虚拟环境,以及常用命令,配置镜像

文章目录背景1.conda的下载地址:2.安装3.执行常用命令1&#xff09;查看版本2&#xff09;查看所有虚拟环境3&#xff09;创建虚拟环境4&#xff09;激活虚拟环境5&#xff09;关闭虚拟环境6&#xff09;删除虚拟环境7&#xff09;创建python2.7的虚拟环境8&#xff09;使用pyt…

命令行上的数据科学第二版 二、开始

原文&#xff1a;https://datascienceatthecommandline.com/2e/chapter-2-getting-started.html 贡献者&#xff1a;Ting-xin 在这一章中&#xff0c;我需要确定你能够利用命令行做数据科学&#xff0c;为此你需要能满足一些条件。条件主要分为三个部分&#xff1a;&#xff08…

SQLyog图形化界面工具【超详细讲解】

目录 一、SQLyog 介绍 二、SQLyog 社区版下载 三、SQLyog 安装 1、选择Chinese后点击OK 2、点击“下一步” 3、选择“我接受”后点击“下一步” 4、点击“下一步” 5、修改安装位置&#xff08;尽量不要安装在C盘&#xff09;&#xff0c;点击“安装” 6、安装后点击“…
最新文章