2. 有2个数组..里面有 N 个整数。
设计一个算法O(nlog2(n)),看是否两个数组里存在一个同样的数。
/*
2. 有2个数组..里面有 N 个整数。
设计一个算法O(nlog2(n)),看是否两个数组里存在一个同样的数。
快排,线性扫描
*/
#include
#include
using namespace std;
#define N 100
bool findSame(int *a,int len1,int *b,int len2,int *result)
{
int i,j;
i=j=0;
sort(a,a+len1);
sort(b,b+len2);
while(i{
if(a[i] ++i;
else if(a[i]>b[j])
++j;
else
{
*result=a[i];
return true;
}
}
return false;
}
int main()
{
int i,a[N],b[N],len1,len2,result;
while(1)
{
cout cin>>len1;
if(len1==-1) break;
cout for(i=0;icin>>a[i];
cout cin>>len2;
cout for(i=0;icin>>b[i];
if(findSame(a,len1,b,len2,&result))
cout else
cout }
return 0;
}
/*
6
1 3 5 6 8 4
5
9 7 3 2 0
-1
*/