A106103. 找数 题解

题目链接：[GESP202603 五级] 找数

这题有好几种思路，我在这里介绍我在考试时用的方法。

我们可以参考归并排序中合并两个数组的过程。对于序列 $A$ 和 $B$ ，先进行从小到大排序，随后令 $i=1, j=1$，从 $A$ 和 $B$ 序列的第一个元素开始比较 $A_i$ 和 $B_j$：若 $A_i$ 等于 $B_j$，则结果数加 1，$i$ 和 $j$ 都后移一位；若 $A_i<B_j$，说明与 $B_j$ 相等的元素应该在 $A_i$ 之后，$i$ 后移一位；若 $A_i>B_j$，说明与 $A_i$ 相等的元素在 $B_j$ 之后，$j$ 后移一位。最终遍历完成后输出答案即可。得 25 分。

代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 100;
int n, m, a[N], b[N], ans;

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 && j<=m; ) {
        if (a[i] == b[j]) i++, j++, ans++;
        else if (a[i] < b[j]) i++;
        else j++;
    }

    cout << ans;

    return 0;
}