五级 202603 找数 题解

P15799 [GESP202603 五级] 找数 题解

洛谷题目传送门

闲话：考试时先写了个暴力，发现纯暴力都能拿大约 $$22$$ 分，很神秘。

题目大意和思路：

给你两个整数类型的数组，分别为数组 $A$ 和数组 $B$，问你在两数组内都出现的数的个数。

显然在 $1≤n,m≤10^5$ 的情况下用暴力无法通过，所以我首先就想到了用 map 来实现，而且通过 map 也可以解决因为 $1≤a_i,b_i≤10^9$ 时要循环查找的东西太多导致超时的情况。

这道题我用 map 的思路就是通过循环将两个数组中所有的数字存进一个 map 类型的数组里，只要出现就在 map 类型的数组里对应数字的个数增加一，最后判断 map 类型的数组中有多少个数字个数为 $2$ 的数再输出就行了。

代码实现：

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;// 定义一个 map 类型的 mp 数组，开 int 就够用了 
int n,m,a[100005],b[100005],sum;// 根据题目要求定义变量和数组 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){// 输入 A 数组中的数 
		cin>>a[i];
		mp[a[i]]++;// 在 mp 数组中做操作 
	}
	for(int i=1;i<=m;i++){// 输入 B 数组中的数 
		cin>>b[i];
		mp[b[i]]++;// 在 mp 数组中做操作
	}
	for(auto i:mp){// 循环判断在 mp 数组中有多少个数字出现了两次 
		if(i.second==2){// 判断 
			sum++;// 答案增加 
		}
	}
	cout<<sum;// 输出答案 
}

完结撒花。