题目描述
给定两个整数可重复集合,求两个集合的交集。
输入
输入有两组数据,第一组的第一行为一正整数n,一下n个正整数ai(0 < i <= n)。
第二组的第一行为正整数m,以下m个正整数bi(0 < i <= m)。
其中 1 < n, m <= 32767 0 < ai, bi <= 32767
输出
输出一行,k个正整数,为两组数据构成集合{ai}和{bi}的交集。
输出按第二组数据出现的顺序输出,两数之间使用空格间隔,最后一个数无空格,重复数据只输出一次。
若交集为空,只输出一个0
样例输入
10
1 2 3 4 5 6 7 8 9 10
10
9 10 11 12 13 14 15 16 17 1
样例输出
9 10 1
有思路,但是时间超限
#include<stdio.h>
void ab(int &i,int &n,int &m,int a[],int b[])
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&b[i]);
}
}
int a[32767];
int b[32767];
int main()
{
int i,j,n,m,k=0,flag=0;
ab(i,n,m,a,b);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(b[i]==a[j])
{
printf("%d ",b[i]);
flag=1;
break;
}
}
}
if(flag==0)
{
printf("%d",0);
}
}
我用的qt写出来的,代码都类似,稍微修改就好了。
思路是将数组b转化为List容器,通过indexOf就能很好判断a中的数据是否在b中。
你的代码循环了n*n次,我的代码循环了n+n次,时间大大缩短了。
int a[] ={1,2,3,4,5,6,7,8,9,10};
int b[]= {9 ,10 ,11 ,12, 13 ,14, 15, 16 ,17, 1};
QList<int> list_b;
for(int i=0;i<10;i++)
{
list_b.append(b[i]);
}
for(int i=0;i<10;i++)
{
int index=-1;
index=list_b.indexOf(a[i]);
if(index<0)
{
qDebug()<<a[i];//打印
}
}
简单做法,就是对于第二个数组中的每个元素,检索是否在第一个数组中,在就输出,并进行计数 。最终如果计数 为0,则输出0
函数名随便定义的