洛谷P15799 [GESP202603 五级] 找数 题解

题目描述给定一个包含 n 个互不相同的正整数的数组 A 与一个包含 m 个互不相同的正整数的数组 B请你帮忙计算有多少个数在数组 A 与数组 B 中均出现。输入格式第一行包含两个整数 n,m。第二行包含 n 个正整数 a_1,a_2,......,a_n 表示数组 A。第三行包含 个正整数 $b_1,b_2,......,b_m 表示数组 B。输出格式输出一个整数表示在数组 与数组 中均出现的数的个数。输入输出样例 #1输入 #13 5 4 2 3 3 1 5 4 6输出 #12说明/提示样例解释样例 1 中4、3 在数组 A 与 B 中均出现。数据范围对于 40% 的数据保证 1≤ n,m ≤ 1000。对于 100% 的数据保证 1 ≤ n,m ≤ 10^51 ≤ a_i,b_i ≤ 10^9。解题思路方法一采用二分查找1.1.1方法遍历数组A每次用二分查找搜索数组B中有没有数组A中的数统计后输出1.1.2样例做法在B数组中寻找4发现B数组中有4count加1在B数组中寻找2发现B数组中没有2count不变在B数组中寻找3发现B数组中有3count加1最终count 2输出结果1.2.1代码AC 记录https://www.luogu.com.cn/record/280812283#includebits/stdc.h using namespace std; int main() { int n,m; scanf(%d%d,n,m);//读入 int a[n1],b[m1],cnt0;//cnt存储最终结果 for(int i1;in;i) scanf(%d,a[i]);//输入A数组 for(int i1;im;i) scanf(%d,b[i]);//输入B数组 sort(a1,an1);//排序 sort(b1,bm1);//二分只针对于有序数组 for(int i1;im;i) {//枚举数组 int l1,rn;//l为左边界r为右边界 while(lr) {//二分查找 int mid(lr)/2;//查找中间值 if(a[mid]b[i]) rmid-1; else lmid1; } if(a[l]b[i]) cnt;//更新cnt } printf(%d,cnt);//输出结果 return 0; }方法二采用STL解题2.1.1什么是STLSTL是一套内置的通用工具库核心组成如下容器存储数据的结构。vector动态数组、map键值对、set唯一元素、list链表等。迭代器类似指针用于遍历容器如 begin()、end()。算法操作容器的函数。sort()排序、find()查找、copy()复制等。本题主要使用map2.1.2map基础使用方法操作类别函数/方式示例代码说明声明std::mapKeyType, ValueTypestd::mapstd::string, int ages;按键自动升序排列插入[]运算符ages[Alice] 25;键不存在则插入存在则覆盖insertages.insert({Bob, 30});键已存在时会忽略插入访问[]运算符ages[Alice];不安全键不存在会创建默认值at()函数ages.at(Bob);安全键不存在抛出std::out_of_range查找find()auto it ages.find(Bob);返回迭代器若不存在返回end()检查存在count()if (ages.count(Bob))存在返回 1不存在返回 0删除erase()ages.erase(Alice);按键值删除大小size()int len ages.size();返回键值对个数判空empty()if (ages.empty())无元素时返回 true遍历范围 forfor (auto p : ages)p.first为键p.second为值清空clear()ages.clear();删除所有元素2.2.1解题方法将数字作为键将是否出现过作为值一一对应在存入A数组时修改值在输入B数组是判断是否出现过此数并修改count输出count2.3.1代码AC 记录 : https://www.luogu.com.cn/record/273884639#includebits/stdc.h using namespace std; unordered_mapint,boolmp; int main() { int n,m; cinnm;//输入 int a[n1],b[m1],cnt0; for(int i1;in;i) { cina[i]; mp[a[i]]1;//将a[i]标记为true } for(int i1;im;i) { cinb[i];//输入B数组中的数 if(mp[b[i]]) cnt;//判断此数是否在A数组中出现过并修改cnt的值 } coutcnt;//输出结果 return 0; }