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

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

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

//輸出：{2,7,8}

[思路1]：

判斷a數組元素值的元素是否在b中，是則輸出之。

時間復雜度：O（n2）

[cpp] 
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）

//快排之分割
[cpp] 
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），典型的以空間換時間的方法。

[cpp] 
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; 
} 
       或者大家有什麼更好的方法，歡迎討論，謝謝！