如 a[M] b[N]

1. 最傻瓜式
   每一次從b數(shù)組中取一值，然后在a數(shù)組里逐個(gè)比較是否相等，該算法復(fù)雜度為 O(MN)

2. 二分查找
   從一個(gè)數(shù)組中取出值后再另一個(gè)數(shù)組中用二分查找法找是否有相等的，算法復(fù)雜度為O(M * lgN)或 O(N * lgM)

3. 用hashtable
   先把a(bǔ)中的值存在hashtable里，然后對(duì)于每一個(gè)b中的值，判斷是否在a中存在，因?yàn)閔ashtable查找的平均復(fù)雜度為 O(1), 所以，整個(gè)算法復(fù)雜度為O(N), 但是，這里的空間復(fù)雜度為 O(M) 。但是，這種方法適合數(shù)組比較小的情況。因?yàn)槿绻鸻數(shù)組比較大，hashtable會(huì)出現(xiàn)collision的情況，這樣，查找的平均復(fù)雜度就不再是 O(1)。

4. 算法復(fù)雜度O(M + N)

void arrayJiao(int ar[], int a_len, int br[], int b_len, int tmp[])  
{  
    int i = 0, j = 0, k = 0;  
    while(i < a_len && j < b_len)  
    {  
        if(ar[i] < br[j])  
            i++;  
        if(ar[i] > br[j])  
            j++;  
        if(ar[i] == br[j])  
        {  
            tmp[k++] = ar[i];  
            i++;  
            j++;  
        }  
    }  
  
    for(i = 0; i < k; ++i)  
    {  
        cout<<tmp[i]<<" ";  
    }  
    cout<<endl;  
}