A20853. 找数
填空题
困难
知识点
题目描述
找数
题目描述
给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B，请你帮忙计算有多少数在数组A与数组B中均出现。
输入格式
第一行包含两个整数n,m。
第二行包含n个正整数a1,a2,...,an表示数组A。
第二行包含m个正整数b1,b2,...,bm表示数组B。
输出格式
输出一个整数，表示在数组A与数组B中均出现的数的个数。
样例
输入样例
3 5
4 2 3
3 1 5 4 6输出样例
2样例解释
样例 1 中，4、3 在数组A与B中均出现。
数据范围
对于40%的数据，保证1≤n,m≤1000。
对于100%的数据，保证1≤n,m≤105,1≤ai,bi≤109。
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m, l, r, mid;
bool ok;
cin >> n >> m;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a.begin(), a.end());
int ans = 0;
for(int i = 0, b; i < m; i++) {
cin >> b;
ok = false;
l = 0;
r = n-1;
while(l <= r)
{
mid = l + (r-l)/2;
if(a[mid] > b) r = mid - 1;
else if(a[mid] < b) l = mid + 1;
else
{
ok = true;
break;
}
}
if(ok) ans++;
}
cout << ans;
return 0;
}
上一题
下一题