洛谷 P15799：[GESP202603 五级] 找数 ← 集合 + STL set

​【题目来源】
https://www.luogu.com.cn/problem/P15799

【题目描述】
给定一个包含 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≤10^5，1≤ai​,bi​≤10^9。

【算法分析】
● STL set 常用函数解析：
https://blog.csdn.net/hnjzsyjyj/article/details/145528031
https://blog.csdn.net/hnjzsyjyj/article/details/127017796

● STL set 中的元素自构“递增无重”。​​​​​​​

● STL set 中的 count(x) 返回集合中元素 x 的个数。由于集合中所有元素的个数是唯一的，所以若 x 在集合中，返回 1，若 x 不在集合中，返回 0。​​​​​​​

【算法代码】

#include <bits/stdc++.h>
using namespace std;

set<int> s;

int main() {
    int n,m;
    cin>>n>>m;
    for(int i=0; i<n; i++) {
        int x;
        cin>>x;
        s.insert(x);
    }

    int cnt=0;
    for(int i=0; i<m; i++) {
        int x;
        cin>>x;
        if(s.count(x)) cnt++;
    }
    cout<<cnt;

    return 0;
}

/*
in:
3 5
4 2 3
3 1 5 4 6

out:
2
*/

【参考文献】
https://mp.weixin.qq.com/s/B2fUqZ_1hRnSgc5z1unr_A
https://blog.csdn.net/hnjzsyjyj/article/details/145528031
https://blog.csdn.net/hnjzsyjyj/article/details/127017796


 

​