0
已解决
高级天翼
2784 重合
经验值：0 时间限制：1000毫秒
题目描述 Description
给定两个数组，输出两个数组重合的元素。
输入描述 Input Description
输入第一行，有两个数n,m，n表示第一个数组长度，m表示第二个数组长度。
第二行，n个正整数
第三行，m个正整数
输出描述 Output Description
重合的元素按照第一个数组顺序输出
样例输入 Sample Input
4 3
2 15 6 8
8 9 2
样例输出 Sample Output
2 8
数据范围及提示 Data Size & Hint
1<=n,m<=100000
每个数范围最大为10^10
---------------------------------------------
有人会用二分做吗？
但是二分不是用于有序数组的吗？
是不是要先排序？
跪求大佬给出思路
李瑞曦在2021-04-29 19:00:52追加了内容
ding
0
已采纳
高级光能
由题意可得知，答案是按照第一个数组顺序输出的。
因此我们可以任意改变b数组中元素的顺序，即排序b数组。
排序后，b就是一个有序的数组了。遍历n个正整数，二分数组b即可
0
资深守护
bool f(int x){
int l=1,r=m+1;
while(l<r){
int mid=(l+r)/2;
if(b[mid]==x)return true;
if(b[mid]>x)r=mid;
else l=mid+1;
}
return false;
}
杜承俊在2021-04-29 18:25:55追加了内容
这是check函数
0
资深守护
要排序
0
高级守护
先排序，再用二分查找，最后按原数组输出
