13038.找数

markdown
复制
1# 找数 题解
2
3## 题目分析
4
5本题给出两个互不相同的正整数数组 $A$ 和 $B$，长度分别为 $n$ 和 $m$。要求统计同时在两个数组中出现的元素个数。
6
7- 数据范围：$1 \leq n,m \leq 10^5$，元素值域 $1 \leq a_i,b_i \leq 10^9$。
8- 数组中所有元素互不相同，因此我们不需要考虑重复计数的问题。
9- 朴素的两层循环比较时间复杂度为 $O(nm)$，在 $10^5$ 规模下会超时，需要更高效的算法。
10
11## 解题思路
12
13由于只需要判断数组 $B$ 中的每个元素是否在数组 $A$ 中出现，我们可以采用**二分查找**（或使用哈希表）来加速查找过程。
14
15具体方法：
161. 将数组 $A$ 排序。排序后可以支持二分查找。
172. 遍历数组 $B$，对 $B$ 中的每一个元素，在排序后的 $A$ 中二分查找。
183. 如果找到，则将答案计数器加一。
194. 最终输出计数器的值。
20
21这样可以将查找的复杂度从 $O(n)$ 降低到 $O(\log n)$，整体复杂度大幅下降，满足题目要求。
22
23## 算法说明
24
25### 二分查找
26
27二分查找是一种在有序序列中快速定位元素的方法。基本步骤如下：
28- 设定查找区间左右边界 `l = 0, r = n-1`。
29- 当 `l <= r` 时，重复以下过程：
30  - 计算中间位置 `mid = l + (r - l) / 2`。
31  - 如果 `a[mid] == target`，则找到了目标，返回成功。
32  - 如果 `a[mid] > target`，说明目标可能在左半部分，更新 `r = mid - 1`。
33  - 如果 `a[mid] < target`，说明目标可能在右半部分，更新 `l = mid + 1`。
34- 如果循环结束还没有找到，则目标不在数组中。
35
36因为数组 $A$ 中的所有元素互不相同，二分查找不会遇到重复值的困扰。
37
38### 参考代码解释
39
40```cpp
41#include <iostream>
42#include <vector>
43#include <algorithm>
44using namespace std;
45
46int main() {
47    int n, m, l, r, mid;
48    bool ok;
49    cin >> n >> m;
50    vector<int> a(n);
51    for(int i = 0; i < n; i++)   // 读入数组 A
52        cin >> a[i];
53    sort(a.begin(), a.end());    // 对 A 排序
54    int ans = 0;
55    for(int i = 0, b; i < m; i++) { // 遍历数组 B
56        cin >> b;
57        ok = false;
58        l = 0;
59        r = n-1;
60        while(l <= r) {          // 二分查找
61            mid = l + (r-l)/2;   // 防止溢出
62            if(a[mid] > b) r = mid - 1;
63            else if(a[mid] < b) l = mid + 1;
64            else {
65                ok = true;       // 找到
66                break;
67            }
68        }
69        if(ok) ans++;            // 统计成功次数
70    }
71    cout << ans;
72    return 0;
73}

代码要点：

• 使用 vector<int> 存储数组 $A$，方便动态管理内存。
• sort(a.begin(), a.end()) 将数组 $A$ 从小到大排序。
• 读入数组 $B$ 时采用边读边查的方式，节省内存和 IO 时间。
• 二分查找中，注意 mid = l + (r - l) / 2 可以避免直接写 (l + r) / 2 时可能出现的整数溢出。
• 引入布尔变量 ok 标记是否找到，最后累加到答案中。

时间复杂度分析

• 排序 $A$：$O(n \log n)$。
• 对 $B$ 中 $m$ 个元素各进行一次二分查找：每次 $O(\log n)$，总计 $O(m \log n)$。
• 总时间复杂度：$O((n+m) \log n)$。
• 空间复杂度：$O(n)$（存储数组 $A$）。

在 $n, m \leq 10^5$ 的情况下，这个复杂度完全可以在 1 秒内完成。

总结

本题是二分查找（或哈希表）的经典应用，考察了将无序查找转化为有序查找的优化思想。对于这类“集合求交”问题，排序加二分是一种常见且高效的解决方案。