欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客-求交集(二分)

程序员文章站 2024-03-17 15:04:40
...

链接: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;
}