P15799 [GESP202603 五级] 找数

题目描述

给定一个包含 $n$ 个互不相同的正整数的数组 $A$ 与一个包含 $m$ 个互不相同的正整数的数组 $B$，请你帮忙计算有多少个数在数组 $A$ 与数组 $B$ 中均出现。

输入格式

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

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$ 表示数组 $A$。

第三行包含 $m$ 个正整数 $b_1,b_2,\cdots ,b_m$ 表示数组 $B$。

输出格式

输出一个整数，表示在数组 $A$ 与数组 $B$ 中均出现的数的个数。

输入输出样例 #1

输入 #1

3 5
4 2 3
3 1 5 4 6

输出 #1

2

说明/提示

样例解释

样例 1 中，$4$、$3$ 在数组 $A$ 与 $B$ 中均出现。

数据范围

对于 $40\%$ 的数据，保证 $1\le n,m\le 1000$。

对于 $100\%$ 的数据，保证 $1\le n,m\le 10^5$，$1\le a_i,b_i\le 10^9$。

解析

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

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int n,m;
int ans=0;
int main(){
    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;
	return 0;
}

2.使用map的解法

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,cnt=0;
map <int,int> mp;
int main(){
	cin>>n>>m;
	while(n--){
		cin>>a;
		mp[a]++;
	}
	while(m--){
		cin>>b;
		if (mp[b]>0){
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
int n,m;
int ans=0;
int main(){
    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++;
        }else if(a[i]<b[j]){//ai小，换下一个
            i++;
        }else{//相等，多一对相等的
            ans++;
            i++;
            j++;
        }
    }
    cout<<ans;
	return 0;
}

另一种双指针解法：

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int b[100005];
int n,m;
int ans=0;
int main(){
    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;
	return 0;
}