求兩無序不重複數組的交集

//輸入：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] << "\t";
                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] << "\t";
                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 << "\t"; //兩次累加-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 << "\t"; 
          }
    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\t",Element[i]);
     }
     printf("\n");
 }
 
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");
}