求两个数组的交集
数组a和b中有许多不同的、未排序的元素，要求找出它们的交集放到数组C中,要求尽可能快的算法
函数定义如下：
size_t intersect(const int a[], int nmema, const int b[], int nmemb, int c, int nmemc);
我的想法是先通过快速排序分别将它们排序，快速排序的时间复杂度为O(nlgn)
因为原数组不能更改所以复制数组还要加上O(n)
然后

C/C++ code

for (i = j = k = 0; ) {   if (a[i] == b[j]) {      c[k++] = a[i];      i++; j++;   } else if (a[i] < b[j])       i++;   else      j++;}

这样总的时间复杂度就是 2*O(n) + 2*O(nlgn) + 2*O(n)
请大家发表一下见解，有没有更好的算法？谢谢


[解决办法]
如果每个数组元素都不一样，而且数组内的元素不是很大的话，可以申请空间进行位图排序：
对数组a搜索元素，将各元素对应的位标记出来
然后对数组b进行搜索，顺序下去，如果在对应的位已经被a标识出来，那说明该元素是交集，放到c中

这样的话，时间也就是o（n+m）

[解决办法]
在你的想法稍微改进下，只排序一个数组，另外一个数组的元素用二分查找看有没有在排序数组里面，应该就是2O(n)+2O(nlgn)
[解决办法]

探讨

在你的想法稍微改进下，只排序一个数组，另外一个数组的元素用二分查找看有没有在排序数组里面，应该就是2O(n)+2O(nlgn)

[解决办法]
参考这个

C/C++ code

#include <algorithm>#include <iostream>#include <functional>#include <cstring>using namespace std;int main() {    char *Alphabet = "abcdefghijklmnopqrstuvwxyz" ;    char *Vowels   = "aeiou" ;    char *AlphaNum = "0123456789abcdef" ;    char result[45] ;    char *last ;    int lenA  = strlen(Alphabet) ;    int lenV  = strlen(Vowels  ) ;    int lenAN = strlen(AlphaNum) ;    cout << "Alphabet = " << Alphabet << endl ;    cout << "Vowels   = " << Vowels   << endl ;    cout << "AlphaNum = " << AlphaNum << endl ;    cout << "\nusing non-predicate versions" << endl ;    //non-predicate set_difference    last = set_difference(Alphabet, Alphabet+lenA,                          AlphaNum, AlphaNum+lenAN,                          result) ;    *last = 0 ;    cout << "set_difference(Alphabet, AlphaNum) =  " << result << endl ;    //non-predicate set_intersection    last = set_intersection(Alphabet, Alphabet+lenA,                            AlphaNum, AlphaNum+lenAN,                            result) ;    *last = 0 ;    cout << "set_intersection(Alphabet, AlphaNum) =  " << result << endl ;    //non-predicate set_symmetric_difference    last = set_symmetric_difference(Alphabet, Alphabet+lenA,                                    Vowels  , Vowels  +lenV,                                    result) ;    *last = 0 ;    cout << "set_symmetric_difference(Alphabet, Vowels) =  " << result << endl ;    //non-predicate set_union    last = set_union(Alphabet, Alphabet+lenA,                     AlphaNum, AlphaNum+lenAN,                     result) ;    *last = 0 ;    cout << "set_union(Alphabet, AlphaNum) =  " << result << endl ;    cout << "\nusing predicate versions" << endl ;    //predicate set_difference    last = set_difference(Alphabet, Alphabet+lenA,                          AlphaNum, AlphaNum+lenAN,                          result  , less<char>()) ;    *last = 0 ;    cout << "set_difference(Alphabet, AlphaNum) =  " << result << endl ;    //predicate set_intersection    last = set_intersection(Alphabet, Alphabet+lenA,                            AlphaNum, AlphaNum+lenAN,                            result  , less<char>()) ;    *last = 0 ;    cout << "set_intersection(Alphabet, AlphaNum) =  " << result << endl ;    //predicate set_symmetric_difference    last = set_symmetric_difference(Alphabet, Alphabet+lenA,                                    Vowels  , Vowels  +lenV,                                    result  , less<char>()) ;    *last = 0 ;    cout << "set_symmetric_difference(Alphabet, Vowels) =  " << result << endl ;    //predicate set_union    last = set_union(Alphabet, Alphabet+lenA,                     AlphaNum, AlphaNum+lenAN,                     result  , less<char>()) ;    *last = 0 ;    cout << "set_union(Alphabet, AlphaNum) =  " << result << endl ;    return 0 ;} 
 
[解决办法]
用STL的MAP就行
[解决办法]
我就写一个简单的例子程序吧

C/C++ code
#include <iostream>#include <map>using namespace std;//计算arr1,arr2的交集int main(){    int arr1[5] = {4,7,3,6,2};    int arr2[5] = {9,0,5,7,3};    map<int, int> result;    for(int i=0;i<5;i++)        result[ arr1[i] ]++;    for(int i=0;i<5;i++)        result[ arr2[i] ]++;    map<int, int>::iterator iter;    for(iter=result.begin();iter!=result.end();iter++)        if(2 == iter->second)            cout << iter->first << " ";    cout << endl;    return 0;}
[解决办法]
数据多就hash法。