如 a[M] b[N]
最傻瓜式
每一次從b數(shù)組中取一值，然后在a數(shù)組里逐個比較是否相等苛茂，該算法復雜度為 O(MN)二分查找
從一個數(shù)組中取出值后再另一個數(shù)組中用二分查找法找是否有相等的已烤，算法復雜度為O(M * lgN)或 O(N * lgM)用hashtable
先把a中的值存在hashtable里，然后對于每一個b中的值妓羊，判斷是否在a中存在胯究，因為hashtable查找的平均復雜度為 O(1), 所以，整個算法復雜度為O(N), 但是侍瑟，這里的空間復雜度為 O(M) 唐片。但是，這種方法適合數(shù)組比較小的情況涨颜。因為如果a數(shù)組比較大费韭，hashtable會出現(xiàn)collision的情況，這樣庭瑰，查找的平均復雜度就不再是 O(1)星持。算法復雜度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;
}
