求两无序不重复数组的交集

//输入：a[]={5,7,8,9,1,2,3 }; b[]={2, 8,10,4,6,7};//输出：{2,7,8}

[思路1]：

判断a数组元素值的元素是否在b中，是则输出之。

时间复杂度：O（n2）

void  cmpInterSection(int a[], int b[], int m, int n){    for(int i = 0; i < m; i++)    {        for(int j = 0;j < n; j++)        {            if(a[i] == b[j])            {                cout << a[i] << "	";                break;            }        }//end for j    }//end for i    cout << endl;}

[思路2]：

1）对两数组进行排序；

2）一次循环判断a和b中元素是否相等，相等则输出；不等则小的值++。

时间复杂度：O（nlogn）

//快排之分割

int divided(int nArr[], int nLeft, int nRight){    int pivot = nArr[nLeft];        while(nLeft < nRight) //×¢ÒâwhileÑ­»•    {        while(nLeft < nRight && nArr[nRight] >= pivot)  //×¢ÒâµÈºÅ        {            --nRight;        }        nArr[nLeft] = nArr[nRight];        while(nLeft < nRight && nArr[nLeft] <= pivot)   //×¢ÒâµÈºÅ        {            ++nLeft;        }        nArr[nRight] = nArr[nLeft];    }        nArr[nLeft] = pivot;    return nLeft;}  //快排之递归void quickCurve(int nArr[], int nLeft, int nRight){    int nPivotPos = 0;    if(nLeft < nRight)    {        nPivotPos = divided(nArr,nLeft,nRight);        quickCurve(nArr,nLeft,nPivotPos-1);        quickCurve(nArr,nPivotPos+1,nRight);    }}//快排void quickSort(int nArr[], int nLen){    quickCurve(nArr,0,nLen-1);}void interSectionOfArray(int a[], int b[], int m, int n){    //快排    quickSort(a,m);    quickSort(b,n);      //一次循环筛选出交集.    if( m < n)    {        int j = 0;        int i = 0;        while(i < m)        {            if(a[i] == b[j])            {                cout << a[i] << "	";                i++;                  j++;            }            else if(a[i] > b[j])            {                j++;        //小值++            }            else            {                i++;        //小值++            }        }        cout << endl;    }//end  if}

[思路3]：

hash表存储两数组到一个表中，统计次数累计为2的元素输出即可。

时间复杂度：O（n），典型的以空间换时间的方法。

ypedef struct HASHSET{    int key;  //值    int nCnt; //计数}hashSet;      hashSet* pSetArray = new hashSet[m+n]; //空间换时间    for(int i = 0; i <m+n; i++)    {        pSetArray[i].key = 0;        pSetArray[i].nCnt = -1;    }  //O(n)实现输出…void hashInterSection(hashSet* pSetArray, int a[], int b[], int m, int n){    for(int i = 0; i < m; i++)    {        pSetArray[a[i]].key = a[i];        pSetArray[a[i]].nCnt++;    }    for(int j = 0; j < n; j++)    {        pSetArray[b[j]].key = b[j];        pSetArray[b[j]].nCnt++;    }      for(int k = 0; k < m+n; k++)    {        if(pSetArray[k].nCnt == 1)        {            cout << pSetArray[k].key << "	"; //两次累加-1+1+1=1.        }    }    cout << endl;}

或者大家有什么更好的方法，欢迎讨论，谢谢！

[思路三]网友keynumber指出了存在问题，见下面的评论。笔者的思路三的确非常空间复杂度太高，且不是严格意义上的哈希表，只能算类哈希（呵呵）。

笔者进行了重写，如下：继续欢迎大家讨论。

//[修改后思路3]：构建哈希表插入操作的过程中，如果元素已经插入过，即其哈希地址有值，则该元素必为两数组的交集，打印输出即可。（前提数组中的元素不重复）

以下哈希表的构造是通过除留余数法实现的，处理冲突的方法是通过开放定址法实现的。

//初始设定表长10000.const int g_nLength = 10000;template <typename _Type>class HashTable{public: HashTable(int Length)   //构建哈希表，表长Length {          Element = new _Type[Length];          for(int i=0;i<Length;i++)          {                    Element[i] = -1;          }          this->Length = Length;          Count = 0; }  ~HashTable() {     delete[] Element; }  //求哈希地址 virtual int Hash(_Type Data) {     return Data % Length; //³ýÁôÓàÊý·¨Çó¹þÏ£µØÖ·. }  //开放定址法再哈希 virtual int ReHash(int Index,int Count) {     return ((Index + Count) % Length); // }  //查找元素，若已存在返回true，否则返回false。 virtual bool SerachHash(_Type Data,int& Index) {     Index = Hash(Data);     int Count = 0;      while(Element[Index] != -1 && Element[Index] != Data)     {         Index = ReHash(Index,++Count);     }      return (Data == Element[Index] ? true :false); }  virtual int SerachHash(_Type Data) {     int Index = 0;     if(SerachHash(Data,Index))      {         return Index;      }     else      {        return -1;     } }  // 插入元素 bool InsertHash(_Type Data) {     int Index = 0;     if(Count < Length && !SerachHash(Data,Index))     {         Element[Index] = Data;         Count++;         return true;     }         //在插入的过程中，如果元素已经存在，即为交集元素则打印之.       if(SerachHash(Data,Index))          {              cout << Data << "	";           }    return false; }  //手动设置表长 void SetLength(int Length) {     delete[] Element;     Element = new _Type[Length];     for(int i=0;i<Length;i++)    {        Element[i] = -1;    }     this->Length = Length; }  //移除元素. void Remove(_Type Data) {     int Index = SerachHash(Data);     if(Index != -1)     {         Element[Index] = -1;         Count--;     } }  //清空整个哈希表 void RemoveAll() {     for(int i=0;i<Length;i++)     {         Element[i] = -1;     }     Count = 0; }  void Print() {     for(int i=0;i<Length;i++)     {         printf("%d	",Element[i]);     }     printf("
"); } protected: _Type* Element;           // Hash表 int Length;               // Hash表长度 int Count;                // Hash表当前长度 };  //自定义子类.template <typename _Type>class HashSet : public HashTable<_Type>{public:        HashSet(int nLen):HashTable<_Type>(nLen){}         ~HashSet(){ }         friend void hashInterSection(HashSet<_Type>* pHashSet, int a[], int b[], int m, int n);private: }; //友元函数的实现void hashInterSection(HashSet<int> *pHashSet, int a[], int b[], int m, int n){         for(int i = 0; i < m; i++)         {             pHashSet->InsertHash(a[i]);         }                for(int j = 0; j < n; j++)         {             pHashSet->InsertHash(b[j]);         }         cout << endl; }  void main(){ //       HashSet<int> hashSet(20);          //测试用例1：两数组没有交集//       int a[]={10,9,8,15,14,16,7,33 }; //       int b[]={1,3,5,11,13,17,19};//       int nLena = sizeof(a)/sizeof(a[0]);//       int nLenb = sizeof(b)/sizeof(b[0]);//       hashInterSection(&hashSet,a,b,nLena,nLenb);         //       //用例1测试结果：返回空。                   //测试用例2：两数组相等，所含元素全部相同。//       HashSet<int> hashSet2(20);  //       int aa[]={10,9,8,15,14,16,7,33 }; //       int bb[]={10,9,8,15,14,16,7,33 };//       int nLena = sizeof(aa)/sizeof(aa[0]);//       int nLenb = sizeof(bb)/sizeof(bb[0]);//       hashInterSection(&hashSet2,aa,bb,nLena,nLenb);         //用例2测试结果：返回交集。            //测试用例3：两数组部分相同。          HashSet<int> hashSet3(20);            int aa[]={10,9,8,15,14,16,7,33 };           int bb[]={10,9,8,15,144,166,73,333,55,29};          int nLena = sizeof(aa)/sizeof(aa[0]);          int nLenb = sizeof(bb)/sizeof(bb[0]);          hashInterSection(&hashSet3,aa,bb,nLena,nLenb);          //用例3测试结果：返回交集。          system("pause");}