GESP2026年3月认证C++五级( 第三部分编程题（2）找数）

题目找数两个数组交集 一、故事两支探险队 有两支探险队 A队有 n 个宝藏 B队有 m 个宝藏 每个宝藏都有一个编号整数 国王说“统计一下有多少宝藏同时出现在 A队 和 B队” 二、问题本质非常重要 就是求两个数组的“交集个数” 三、最简单理解暴力方法❌方法1双重循环for(int i0;in;i) for(int j0;jm;j) if(a[i] b[j]) ans;❗问题 时间复杂度O(n × m) 太慢考试会超时 四、聪明方法二分查找故事图书馆找书 A队的书已经整理好了排序 想找一本书 用“二分查找” 五、核心思路必须掌握步骤1️⃣ 先排序 Asort(a.begin(), a.end());2️⃣ 遍历 B对每个 b 去 A 里面找3️⃣ 用二分查找 六、二分查找详解重点1、故事猜数字游戏 你要找一个数l 0, r n-12✨每次mid (l r) / 23、判断if(a[mid] b) r mid - 1; else if(a[mid] b) l mid 1; else 找到了 七、完整代码#include iostream #include vector #include algorithm using namespace std; int main() { int n, m; cin n m; vectorint a(n); // 输入 A for(int i 0; i n; i) cin a[i]; // 排序 A非常关键 sort(a.begin(), a.end()); int ans 0; // 遍历 B for(int i 0, b; i m; i) { cin b; int l 0, r n - 1; bool ok false; // 二分查找 while(l r) { int mid (l r) / 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 endl; return 0; } 八、举个例子1、输入A [4, 2, 3] B [3, 1, 5, 4, 6]2、✨步骤排序 AA [2, 3, 4]3、遍历 B找 3 ✔️找 1 ❌找 5 ❌找 4 ✔️找 6 ❌4、 总共2 个 九、复杂度分析⏱ 时间复杂度排序O(n log n)查找m × O(log n) 总O(n log n m log n) 十、进阶技巧高手必备方法2双指针更快1、 如果两个数组都排序i 指向 A j 指向 B2、同时移动A[i] B[j] → ans A[i] B[j] → i A[i] B[j] → j3、 时间复杂度O(n m) 十一、总结这类题本质查找 优化多种解法比较方法复杂度推荐暴力O(nm)❌二分O(m log n)✔️双指针O(nm)⭐⭐⭐ 十二、考点回顾我们必须掌握1️⃣ 二分查找模板超级重点while(l r){ mid (l r)/2; if(a[mid] x) r mid - 1; else if(a[mid] x) l mid 1; else return true; }2️⃣ 排序 查找组合思维 GESP五级考试很多题都是排序 二分