CCF-GESP计算机学会等级考试2026年3月五级C++T2 找数

P15799 [GESP202603 五级] 找数

题目描述

给定一个包含 nnn 个互不相同的正整数的数组 AAA 与一个包含 mmm 个互不相同的正整数的数组 BBB，请你帮忙计算有多少个数在数组 AAA 与数组 BBB 中均出现。

输入格式

第一行包含两个整数 n,mn,mn,m。

第二行包含 nnn 个正整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​ 表示数组 AAA。

第三行包含 mmm 个正整数 b1,b2,⋯ ,bmb_1,b_2,\cdots,b_mb1​,b2​,⋯,bm​ 表示数组 BBB。

输出格式

输出一个整数，表示在数组 AAA 与数组 BBB 中均出现的数的个数。

输入输出样例 #1

输入 #1

3 5 4 2 3 3 1 5 4 6 

输出 #1

2 

说明/提示

样例解释

样例 1 中，444、333 在数组 AAA 与 BBB 中均出现。

数据范围

对于 40%40\%40% 的数据，保证 1≤n,m≤10001 \leq n,m \leq 10001≤n,m≤1000。

对于 100%100\%100% 的数据，保证 1≤n,m≤1051 \leq n,m \leq 10^51≤n,m≤105，1≤ai,bi≤1091 \leq a_i,b_i \leq 10^91≤ai​,bi​≤109。

解析

1.将a数组和b数组合并排序，相等的数会相邻，找到有多少对相邻的数相等，就是答案，时间复杂度O（NlogN）,(N=n+m),详见代码：

#include<bits/stdc++.h>usingnamespace std;int a[200005];int n,m;int ans=0;intmain(){ cin>>n>>m;for(int i=1;i<=n+m;i++){ cin>>a[i];}sort(a+1,a+n+m+1);for(int i=1;i<n+m;i++){if(a[i]==a[i+1]) ans++;} cout<<ans;return0;}

2.将a，b数组分别排序，用双指针法求相同的数对，时间复杂度O(NlogN)，（N=max(n,m）)，详见代码：

#include<bits/stdc++.h>usingnamespace std;int a[100005];int b[100005];int n,m;int ans=0;intmain(){ cin>>n>>m;for(int i=1;i<=n;i++){ cin>>a[i];}for(int i=1;i<=m;i++){ cin>>b[i];}sort(a+1,a+n+1);//分别排序sort(b+1,b+m+1);int i=1;//a数组的第一个数int j=1;//b数组的第一个数while(i<=n&&j<=m){//都没完if(a[i]>b[j]){//bj小，换下一个 j++;}elseif(a[i]<b[j]){//ai小，换下一个 i++;}else{//相等，多一对相等的 ans++; i++; j++;}} cout<<ans;return0;}

另一种双指针解法：

#include<bits/stdc++.h>usingnamespace std;int a[100005];int b[100005];int n,m;int ans=0;intmain(){ cin>>n>>m;for(int i=1;i<=n;i++){ cin>>a[i];}for(int i=1;i<=m;i++){ cin>>b[i];}sort(a+1,a+n+1);//分别排序sort(b+1,b+m+1);for(int i=1,j=1;i<=n;i++){//枚举a数组的每一个数while(b[j]<a[i]&&j<=m){//bj小于ai，换下一个bj j++;}if(a[i]==b[j]) ans++;//相等，多一对if(j>m)break;//b数组没了，结束} cout<<ans;return0;}