牛客-求交集（二分）

链接：https://www.nowcoder.com/acm/contest/76/C
来源：牛客网

给你两个升序排列的集合，求出两个集合的交集。

输入描述:

有多个测试用例，输入到文件结束。
对于每一个测试用例：
第一行输入两个整数n,m(0<n,m<=1000000),分别代表第一个集合和第二个集合的元素的数量。
第二行输入n个整数，表示第一个集合中的元素，元素之间用空格隔开。
第三行输入m个整数，表示第二个集合中的元素，元素之间用空格隔开。
两个集合中的元素范围在[-1000000000,1000000000]区间内。

输出描述:

每个测试用例用一行来输出两个集合的交集的所有元素（元素用空格隔开且按升序排列），若交集为空则输出"empty"。

示例1

输入

2 3
1 3
1 2 3

输出

1 3

备注:

交集为空的情况下，输出"empty"

题意：》》》

思路：一开始没想到用二分，先想的是map映射一下，时间很短，但是内存超了QAQ,感觉这个题搞法很多，就是注意一下数据范围；

下面附上我的( 错误 )代码：

#include<bits/stdc++.h>
#include<map>
using namespace std;
map<string,int> p;
int n,m;
int main()
{
    while(cin>>n>>m)
    {
        p.clear();
        char s1[15];
        char s2[15];   
        for(int i=0;i<n;i++)
        {
            scanf("%s",s1);
            p[s1]=1;
        }
        int flag=0;
        for(int i=0;i<m;i++)
        {
            scanf("%s",s2);
            if(p[s2]==1)
            {
                flag=1;
                printf("%s ",s2);
            }
        }
        if(!flag)
            puts("empty");
        else
            puts(" ");
    }
    return 0;
}

正确代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000005],b[1000005],c[1000005];
int n,m;
bool find(int x)
{
	int l=0,r=n-1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(a[mid]==x)
			return true;
		else if(a[mid]<x)
			l=mid+1;
		else 
			r=mid-1;
	}
	return false;
}
int main()
{
	while(cin>>n>>m)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		int k=0;
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		for(int i=0;i<m;i++)
		{
			scanf("%d",&b[i]);
			if(find(b[i])==true)
				c[k++]=b[i];
		}
		if(k==0)
			puts("empty");
		else
		{
			for(int i=0;i<k;i++)
				printf("%d%c",c[i],i==k-1?'\n':' ');
		}
	}
	return 0;
}