求教：如何快速找出两个未排序数组的交集元素（时间复杂度和空间复杂度
今天去面试的时候，面试官问了这么个问题：
现有数据A[]和数组B[]，数组A和B的元素个数可能相差很多，但也可能几乎相同。要求有什么方法能尽快找出数组A和B的交集元素。说明时间和空间复杂性是多少？
PS：我当时想的是快速排序，然后比对。时间复杂性是（N*lgN + M*lgM + M + N）,各位有没有好的想法，请赐教啊~
[解决办法]
只要求尽可能快的话，直接计数法，不过浪费空间，要求数的范围不能太大
[解决办法]
小数组建hashtable，建好以后大数组去查这个hashtable
[解决办法]
楼主的想法是对的,先排序,再比对.
[解决办法]
我细化下一二楼的方法。
首先你得存储数组A[]和B[]吧，那么申请一个足够大的数组C[]。
扫描数组A[],并置C[A[i]]<-+1。
然后扫描数组B[],如果发现C[B[i]]>0,那么输出i。
另外如果按照楼主的想法，直接对两个数组排序然后比对，那么怎么比对呢？比对的时间复杂度是O(N+M)吗？
[解决办法]
/*
输出数组a和数组b公共的元素 ，O(n)
例如：
a: 1 2 2 3
b: 3 1 5 6 7
输出：1 3
a: 4 4 4 5
b: 4 4 5 3
输出: 4 4 5
*/
#include<iostream>
#include<string>
using namespace std;
int main(){
int a[105],b[105];
int n,m;
int c[105],cnt; //公共元素存放在数组c中
int num[1005]; //假定数组a,b中的值不超过1000，如果太大开不了这么大的数组，
//应该手写hash函数或者用hash table存储
while(cin>>n>>m){
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<m;i++)
cin>>b[i];
memset(num,0,sizeof(num));
for(int i=0;i<n;i++)
num[ a[i] ]++;
cnt=0;
for(int i=0;i<m;i++){
if( num[ b[i] ] ){
c[cnt++]=b[i];
num[ b[i] ]--;
}
}
for(int i=0;i<cnt;i++)
cout<<c[i]<<" ";
cout<<endl;
}
return 0;
}
