NC15118. 求交集
描述
给你两个升序排列的集合，求出两个集合的交集。
输入描述
有多个测试用例，输入到文件结束。
对于每一个测试用例：
第一行输入两个整数n,m(0<n,m<=1000000),分别代表第一个集合和第二个集合的元素的数量。
第二行输入n个整数，表示第一个集合中的元素，元素之间用空格隔开。
第三行输入m个整数，表示第二个集合中的元素，元素之间用空格隔开。
两个集合中的元素范围在[-1000000000,1000000000]区间内。
输出描述
每个测试用例用一行来输出两个集合的交集的所有元素（元素用空格隔开且按升序排列），若交集为空则输出"empty"。
示例1
输入:
2 3 1 3 1 2 3
输出:
1 3
C++14(g++5.4) 解法, 执行用时: 319ms, 内存消耗: 23076K, 提交时间: 2020-07-17 21:00:41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,x,a[1000010],flag=0;
int main(){
while(~scanf("%d %d",&n,&m)){
flag=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
while(m--){
scanf("%d",&x);
int pos=lower_bound(a,a+n,x)-a;
if(a[pos]==x){
flag=1;
printf("%d ",x);
}
}
if(flag==0)cout<<"empty"<<endl;
else cout<<endl;
}
}
C++11(clang++ 3.9) 解法, 执行用时: 329ms, 内存消耗: 21492K, 提交时间: 2020-02-29 18:09:01
#include<stdio.h>
#include<stdlib.h>
bool a[2000000005];
int main()
{
int n,m;
int x,flag=0;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&x);
a[x+1000000000]=1;
}
for(int i=0;i<m;i++)
{
scanf("%d",&x);
if(a[x+1000000000]==1)
{
if(flag)
printf(" ");
printf("%d",x);
flag=1;
}
}
if(flag==0)
printf("empty");
}