CCF-GESP 2026 年 3 月五级 C++ 真题：找数
题目描述
给定一个包含 n 个互不相同的正整数的数组 A 与一个包含 m 个互不相同的正整数的数组 B，请你帮忙计算有多少个数在数组 A 与数组 B 中均出现。
输入格式
第一行包含两个整数 n, m。
第二行包含 n 个正整数 a[1], a[2], ..., a[n] 表示数组 A。
第三行包含 m 个正整数 b[1], b[2], ..., 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 ≤ n, m ≤ 1000。
对于 100% 的数据，保证 1 ≤ n, m ≤ 10^5，1 ≤ a[i], b[i] ≤ 10^9。
解析
方法一：合并排序法
将 A 数组和 B 数组合并后排序，相等的数会相邻。统计有多少对相邻的数相等，即为答案。时间复杂度 O(N log N)，其中 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;
}
