leetcode 力扣刷题 数组交集(数组、set、map都可实现哈希表)

数组交集

  • 349. 两个数组的交集
    • 排序+双指针
    • 数组实现哈希表
    • unordered_set
    • unordered_map
  • 350. 两个数组的交集Ⅱ
    • 排序 + 双指针
    • 数组实现哈希表
    • unordered_map

349. 两个数组的交集

题目链接:349. 两个数组的交集
题目内容如下,理解题意:①交集中每个元素是唯一的,只能出现一次,所以本题要找的是同时出现在数组nums1和nums2中的元素,但是并不关心他们出现的次数;②输出结果的顺序不用考虑,也就是只要找到了同时出现在nums1和nums2中的元素就行,可以给数组排序(打乱了原本的顺序)再去查找、可以用map、set(其中key是无序的)……
在这里插入图片描述
这个题目暴力求解是可以的,暴力求解两层循环,将nums1和nums2的元素逐个对比,时间复杂度是O(m*n),因为nums1和nums2的长度都<=1000,所以最终也是能够运行的。
考虑更优的解法,直接一遍遍历nums1和nums2就好了。以下详述各解法:

排序+双指针

解法Ⅰ,对nums1和nums2排序后,从头开始遍历两个数组(下标用index1和index2),并将nums1[index1] = nums2[index2]的元素加入结果数组中。
存在的问题是:因为nums1和nums2中存在重复元素,如果找到了nums1[index1] = nums2[index2],且在nums1中,nums1[index1] 有重复,即nums1[index1+1] = nums1[index1] ,且在nums2中,nums2[index2]有重复,即nums2[index2+1] = nums2[index2]。那么直接对index++和index2++,会向结果数组中添加重复的元素。
解决:找到nums1[index1] = nums2[index2]后,index1++直到找到与之不同的下一个元素(就是跳过中间的相同的元素);index2++同样。
在这里插入图片描述

代码实现(C++):

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        sort(nums1.begin(),nums1.end());//先给nums1和nums2都排序
        sort(nums2.begin(),nums2.end());
        //排序后双指针(index1和index2遍历nums1和nums2
        for(int index1 = 0, index2 = 0; index1 < nums1.size() && index2 < nums2.size();){
            if(nums1[index1] == nums2[index2]){
                ans.emplace_back(nums1[index1]);    //如果找到在两个数组中出现的元素,加入到结果数组中
                //之后直接跳过和当前元素相同的一截,避免有可能向ans中重复添加该元素的可能
                do{
                    index1++;
                }while(index1 < nums1.size() && nums1[index1] == nums1[index1 - 1]);
                do{
                    index2++;
                }while(index2 < nums2.size() && nums2[index2] == nums2[index2 - 1]);
            }
            //如果不相等,更小的那个数向后移,同样是跳过和当前元素相同的一截,避免重复的比较
            else  if( nums1[index1] < nums2[index2]){
                do{
                    index1++;
                }while(index1 < nums1.size() && nums1[index1] == nums1[index1 - 1]);                
            }
            else{
                do{
                    index2++;
                }while(index2 < nums2.size() && nums2[index2] == nums2[index2 -1]);                
            }
        }
        return ans;
    }
};

数组实现哈希表

哈希表的好处体现在,它能够快速查找一个元素是否存在,时间复杂度是O(1)。我们要找nums1和nums2中同时存在的元素,换句话——查找nums1中某个元素是否出现在了nums2中。那么就可以用哈希表。因为题目中,nums1和num2的长度以及其中的int元素的大小都给了限制(<=1000),那么可以用数组来实现哈希表。
直接定义长度为1001的int数组count_1和count_2,统计nums1中元素的次数和nums2中元素出现的次数,最后对比count_1和count_2的每位元素,如果同时不为0的话,将对应元素加入到ans中。
代码如下(C++):

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int count_1[1001] = {0}, count_2[1001] = {0};
        vector<int> ans;
        //分别统计nums1和nums2中元素出现情况
        for ( auto& num : nums1){
            count_1[num]=1;
        }
        for ( auto& num : nums2){            
            count_2[num]++;
        }
        for ( int i = 0; i <= 1000; i++){
        	//在两个数组中出现次数均>=1时,加入ans中
            if( count_1[i] && count_2[i])
                ans.emplace_back(i);
        }
        return ans;
    }
};

优化:上面需要用到两个数组count_1和count_2来分别统计nums1、nums2中元素出现的情况,之后还要遍历这俩数组。是否有可能只使用一个count数组,用两次?——遍历nums1的时候,出现的元素不统计次数,而是count[nums[i]]=1,标记该元素出现过;遍历nums2的时候,如果count[nums2[j]] !=0就表示在两个数组中同时存在;防止重复添加,再将count[nums2[j]]=0;
代码实现(C++):

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int count[1001] = {0};
        vector<int> ans;
        //统计nums1中元素的出现情况
        for ( auto& num : nums1){
            count[num]=1;
        }
        //遍历nums2
        for ( auto& num : nums2){
            if(count[num]){ //同时判断nums2中的元素在nums1中是否出现
                count[num]=0;
                ans.emplace_back(num);
            }
        }      
        return ans;
    }
};

unordered_set

题意是要找交集,那么直接把数组变成集合,然后求两个集合交集就好。实现上,将vector变成unordered_set,然后对比两个unordered_set的key,找到重叠部分。
代码实现(C++):

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    	//把vector转化成unordered_set
        unordered_set<int> num_set1(nums1.begin(),nums1.end());
        unordered_set<int> num_set2(nums2.begin(),nums2.end());
        vector<int> ans;
        //遍历两个set,找交集;遍历size小的
        if( num_set1.size() < num_set2.size()){
            for( auto& key : num_set1)
                if(num_set2.count(key))
                    ans.emplace_back(key);
        }
        else{
            for( auto& key :num_set2)
                if(num_set1.count(key))
                    ans.emplace_back(key);
        }
        return ans;
    }
};

unordered_map

最后也能用map来实现,遍历nums1和nums2的同时,统计其中元素出现的次数,用unordered_map来存,key是数组中出现的元素,value是元素出现的次数; 之后找到两个map中重合的key。
代码(C++):

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> count_1, count_2; 
        vector<int> ans;
        //用map统计数组中出现的元素及其次数
        for ( auto& num : nums1){
            count_1[num]++;
        }
        for ( auto& num : nums2){
            count_2[num]++;
        }
        if(count_1.size() < count_2.size()){
            for ( auto key_value : count_1)
                if(count_2.count(key_value.first))
                    ans.emplace_back(key_value.first);
        }
        else{
            for ( auto key_value : count_2)
                if(count_1.count(key_value.first))
                    ans.emplace_back(key_value.first);
        }
        return ans;
    }
};

350. 两个数组的交集Ⅱ

题目链接:350. 两个数组的交集Ⅱ
题目内容:在这里插入图片描述
这道题和上一题唯一不同的点在于:在nums1和nums2中同时出现的元素,如果出现次数不止一次,都需要加入到结果中。即不仅要统计同时出现在nums1和nums2中的元素,还要统计他们各自出现的次数(C1和C2),并在结果数组ans中重复min (C1, C2) 次。以下代码均在上一题基础上做一点改动即可。

排序 + 双指针

排序后数组元素逐个对比就好:双指针index1和index2,每次对比nums1[index1]和nums2[index2]的关系后,直接index1++,index2++:


class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        for(int index1 = 0, index2 = 0; index1 < nums1.size() && index2 < nums2.size();){
            if(nums1[index1] == nums2[index2]){
                ans.emplace_back(nums1[index1]);
                //下标直接向后移动,这样同时重复出现在两个数组中的元素能够重复添加
                index1++;
                index2++;               
            }
            else  if( nums1[index1] < nums2[index2]){
                index1++;              
            }
            else{
                index2++;               
            }
        }
        return ans;
    }
};

数组实现哈希表

先用数组count统计nums1中出现的元素,及其次数;再遍历nums2,同时出现在nums1中的元素,count[nums2[i]]- -,向结果数组ans中添加一次该元素。

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        int count[1001] = {0};
        vector<int> ans;
        //统计出现的元素,以及次数
        for ( auto& num : nums1){
            count[num]++;
        }
        for ( auto& num : nums2){
            if(count[num]){
            	//对于同时出现的元素,对其次数--,保证后续再出现该元素时,还能重复添加
                count[num]--;
                ans.emplace_back(num);
            }          
        }      
        return ans;
    }
};

unordered_map

只是将上面的数组换成了unordered_map。用数组实现哈希表适用于nums1和nums2都不大的,并且其中元素也不大的情况,当数组很大并且数组元素为int,大小没有限制的时候,用map更合适(或者set)
代码如下:

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> count;
        vector<int> ans;
        for(auto& num : nums1){
            count[num]++;
        }
        for(auto& num : nums2){
            if(count.count(num)){
                ans.emplace_back(num);
                count[num]--;
                //如果已经重复添加了min(c1,c2)次了,即便后续再出现也不能再添加了
                if(count[num]==0)
                    count.erase(num);
            }
        }
        return ans;
    }
};

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

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

相关文章

完美解决Github提交PR后报错:File is not gofumpt-ed (gofumpt)

问题阐述 最近在Github上提交PR后&#xff0c;遇到了这么一个问题&#xff1a;golangci-lint运行失败&#xff0c;具体原因是File is not gofumpt-ed (gofumpt)。 名词解释 golangci-lint&#xff1a; golangci-lint 是Go语言社区中常用的代码质量检查工具&#xff0c;它可以…

【C++学习手札】一文带你初识运算符重载

食用指南&#xff1a;本文在有C基础的情况下食用更佳 &#x1f340;本文前置知识&#xff1a; C类 ♈️今日夜电波&#xff1a;クリームソーダとシャンデリア—Edo_Ame江户糖 1:20 ━━━━━━️&#x1f49f;──────── 3:40 …

Linux 僵死进程

fork复制进程之后&#xff0c;会产生一个进程叫做子进程&#xff0c;被复制的进程就是父进程。不管父进程先结束&#xff0c;还是子进程先结束&#xff0c;对另外一个进程完全没有影响&#xff0c;父进程和子进程是两个不同的进程。 一、孤儿进程 现在有以下代码&#xff1a;…

第4章:决策树

停止 当前分支样本均为同一类时&#xff0c;变成该类的叶子节点。当前分支类型不同&#xff0c;但是已经没有可以用来分裂的属性时&#xff0c;变成类别样本更多的那个类别的叶子节点。当前分支为空时&#xff0c;变成父节点类别最多的类的叶子节点。 ID3 C4.5 Cart 过拟合 缺…

TCP服务器—实现数据通信

目录 前言 1.接口介绍 2.编写服务器 3.编写客户端 4.编译链接 5.测试 6.总结 前言 今天我们要介绍的是使用TCP协议实现数据通信&#xff0c;相比于之前写的UDP服务器实现数据信&#xff0c;在主体逻辑上并没有差别。客户端向服务器发送信息&#xff0c;服务器接受信息并回…

时序预测 | MATLAB实现基于CNN-LSTM卷积长短期记忆神经网络的时间序列预测-递归预测未来(多指标评价)

时序预测 | MATLAB实现基于CNN-LSTM卷积长短期记忆神经网络的时间序列预测-递归预测未来(多指标评价) 目录 时序预测 | MATLAB实现基于CNN-LSTM卷积长短期记忆神经网络的时间序列预测-递归预测未来(多指标评价)预测结果基本介绍程序设计参考资料 预测结果 基本介绍 MATLAB实现基…

item_get_sales-获取TB商品销量详情

一、接口参数说明&#xff1a; item_get_sales-获取商品销量详情&#xff0c;点击更多API调试&#xff0c;请移步注册API账号点击获取测试key和secret 公共参数 请求地址: https://api-gw.onebound.cn/taobao/item_get_sales 名称类型必须描述keyString是调用key&#xff08…

vim键盘图

国外&#xff1a;http://www.viemu.com/a_vi_vim_graphical_cheat_sheet_tutorial.html&#xff0c;原创&#xff0c;有SVG图&#xff0c;有分步骤的图。 国内翻译&#xff1a;[https://blog.csdn.net/qq_41052753/article/details/101031847 有几个配色&#xff0c;很高清&…

gitee上传一个本地项目到一个空仓库

gitee上传一个本地项目到一个空仓库 引入 比如&#xff0c;你现在本地下载了一个半成品的框架&#xff0c;现在想要把这个本地项目放到gitee的仓库上&#xff0c;这时就需要我们来做到把这个本地项目上传到gitee上了。 具体步骤 1. 登录码云 地址&#xff1a;https://gite…

mysql 索引 区分字符大小写

mysql 建立索引&#xff0c;特别是unique索引&#xff0c;是跟字符集、字符排序规则有关的。 对于utf8mb4_0900_ai_ci来说&#xff0c;0900代表Unicode 9.0的规范&#xff0c;ai表示accent insensitivity&#xff0c;也就是“不区分音调”&#xff0c;而ci表示case insensitiv…

Patch SCN一键解决ORA-600 2662故障---惜分飞

客户强制重启库之后,数据库启动报ORA-600 2037,ORA-745 kcbs_reset_pool/kcbzre1等错误 Wed Aug 09 13:25:38 2023 alter database mount exclusive Successful mount of redo thread 1, with mount id 1672229586 Database mounted in Exclusive Mode Lost write protection d…

【Docker】Docker network之bridge、host、none、container以及自定义网络的详细讲解

&#x1f680;欢迎来到本文&#x1f680; &#x1f349;个人简介&#xff1a;陈童学哦&#xff0c;目前学习C/C、算法、Python、Java等方向&#xff0c;一个正在慢慢前行的普通人。 &#x1f3c0;系列专栏&#xff1a;陈童学的日记 &#x1f4a1;其他专栏&#xff1a;CSTL&…

在Orangepi5开发板3588s使用opencv获取摄像头画面

先感谢香橙派群的管理员耐心指导&#xff0c;经过不断的调试修改最后成功通过opencv调用mipi摄像头获取画面 就记录分享一下大概步骤希望大家少踩点坑&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 我用的固件系统是ubuntu2022.0.4 固件是&#x…

Cenos7 搭建Minio最新版集群部署服务器(一)

------> 道 | 法 | 术 | 器 | 势 <------ 多台服务器间免密登录|免密拷贝 Cenos7 搭建Minio集群部署服务器(一) Cenos7 搭建Minio集群Nginx统一访问入口|反向动态代理(二) Spring Boot 与Minio整合实现文件上传与下载(三) CentOS7的journalctl日志查看方法 …

ES中倒排索引机制

在ES的倒排索引机制中有四个重要的名词&#xff1a;Term、Term Dictionary、Term Index、Posting List。 Term&#xff08;词条&#xff09;&#xff1a;词条是索引里面最小的存储和查询单元。一段文本经过分析器分析以后就会输出一串词条。一般来说英文语境中词条是一个单词&a…

炒股票怎么加杠杆_融资融券账户怎么开通

炒股票作为一种投资方式&#xff0c;可以带来不错的回报。然而&#xff0c;对于那些希望以较小的资金获得更高收益的投资者来说&#xff0c;加杠杆炒股票是一个值得考虑的选择。本文将为您介绍加杠杆炒股票的意义&#xff0c;以及如何开通融资融券账户。 加杠杆炒股票的意义&a…

FFmpeg 硬编码VideoToolBox流程

介绍 FFmpeg已经提供对 VideoToolBox 的编解码支持&#xff1b;主要涉及到的文件有videotoolbox.c、videotoolbox.h、videotoolboxenc.c、ffmepg_videotoolbox.c。在编译 FFmpeg 源码时&#xff0c;想要支持VideoToolBox&#xff0c;在 configure 时&#xff0c;需要–enable-…

考公-判断推理-逻辑判断-加强类

论点 论据 削弱 论点 转折之后 例题 例题 例题 例题 搭桥方向&#xff0c;论据推出论点 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题 例题

SpringCloud实用篇4——MQ RabbitMQ SpringAMQP

目录 1 初识MQ1.1 同步和异步通讯1.1.1 同步通讯1.1.2 异步通讯 1.2 技术对比 2.快速入门2.1 安装RabbitMQ2.1.1 单机部署2.1.2集群部署 2.2 RabbitMQ消息模型2.3.导入Demo工程2.4 入门案例2.4.1 publisher实现2.4.2 consumer实现 3 SpringAMQP3.1 Basic Queue 简单队列模型3.1…

使用公网访问内网IIS网站服务器【无需公网IP】

使用公网访问内网IIS网站服务器【无需公网IP】 文章目录 使用公网访问内网IIS网站服务器【无需公网IP】前言1. 注册并安装cpolar2. 创建隧道映射3. 获取公网地址 前言 这里介绍通过内网穿透&#xff0c;实现公网访问内网IIS网站服务器。 都知道&#xff0c;现在基本不会被分配…