B1898 【基础】同时出现的数
大约 3 分钟
B1898 【基础】同时出现的数
【算法】 二分查找、排序
【C++】 二分查找、sort、lower_bound
【难度】 普及−
B1898 【基础】同时出现的数
一、题目简述
有两组整数,第一组有 个,第二组有 个。要求找出第二组中哪些数在第一组中出现过,将这些数从小到大输出(如果有重复出现的数也要输出多次)。
数据范围:,数值范围 。
二、解题思路
数据规模分析
和 最大都是 。如果对于第二组的每个数都去第一组中遍历查找,复杂度是 ,显然会超时。
算法选择
先对第一组排序(),然后对于第二组的每个数,用二分查找判断是否在第一组中出现(每次 )。总复杂度 ,可以在时限内通过。
具体步骤:
- 对第一组数组
a[]排序 - 遍历第二组数组
b[],对每个b[i]使用lower_bound在a中查找 - 如果找到了(即返回值对应的元素等于
b[i]),把b[i]加入答案列表 - 最后对答案列表排序,输出
关于重复数
题目要求"包含重复的",意思是如果第二组中某个数出现了多次,且该数也在第一组中出现,则答案中该数也要出现对应次数。我们的做法中,每次查找都是独立的,自然会保留重复。
手动模拟
假设第一组:,第二组::
- 第一组排序后:
- 遍历第二组:
- :
lower_bound在排序数组中找到位置 1, 匹配,ans加入 1 - :找不到,跳过
- :找到位置 3, 匹配,
ans加入 3 - :找到位置 1, 匹配,
ans加入 1
- :
ans = [1, 3, 1],排序后输出:1 1 3
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
// 对第一组排序
sort(a + 1, a + n + 1);
vector<int> ans;
for (int i = 1; i <= m; i++) {
// 用 lower_bound 查找 b[i] 是否在 a 中出现
int pos = lower_bound(a + 1, a + n + 1, b[i]) - a;
if (pos <= n && a[pos] == b[i]) {
ans.push_back(b[i]);
}
}
// 对结果排序
sort(ans.begin(), ans.end());
for (int x : ans) printf("%d ", x);
printf("\n");
return 0;
}四、复杂度分析
- 时间复杂度:排序第一组 , 次二分查找 ,排序答案列表最坏 。总复杂度 。
- 空间复杂度:两个静态数组 ,答案列表 ,总 。
五、易错点
- 直接两重循环会超时:,远超过每秒 的承受范围。
lower_bound返回值判断:必须同时检查pos <= n(防止越界)和a[pos] == b[i](确认真的找到了)。lower_bound只是找第一个 的位置,不代表找到了相等的值。- 输出顺序:题目要求从小到大输出,所以答案列表需要最后排一次序。也可以在遍历第二组之前就决定好输出顺序,但最后排序更简单直接。
