学步园

2.  有2个数组..里面有 N 个整数。
设计一个算法O(nlog2(n))，看是否两个数组里存在一个同样的数。

/*
2.  有2个数组..里面有 N 个整数。
设计一个算法O(nlog2(n))，看是否两个数组里存在一个同样的数。	

快排,线性扫描
*/
#include<iostream> 
#include<algorithm> 
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<len1&&j<len2) 
	{ 
		if(a[i]<b[j])    
			++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<<"请输入数组1元素的个数n(-1结束)："<<endl;
		cin>>len1;
		if(len1==-1) break;
		cout<<"请输入"<<len1<<"个元素："<<endl;
		for(i=0;i<len1;i++)
			cin>>a[i]; 
			
		cout<<"请输入数组2元素的个数n："<<endl;
		cin>>len2;
		cout<<"请输入"<<len2<<"个元素："<<endl;
		for(i=0;i<len2;i++)
			cin>>b[i]; 
		if(findSame(a,len1,b,len2,&result)) 
			cout<<result<<endl; 
		else
			cout<<"None"<<endl;
	} 
	return 0; 
} 
/*
6
1 3 5 6 8 4 
5
9 7 3 2 0
-1
*/