两个排序数组的交集

如 a[M] b[N]

  1. 最傻瓜式
    每一次从b数组中取一值,然后在a数组里逐个比较是否相等,该算法复杂度为 O(MN)

  2. 二分查找
    从一个数组中取出值后再另一个数组中用二分查找法找是否有相等的,算法复杂度为O(M * lgN)或 O(N * lgM)

  3. 用hashtable
    先把a中的值存在hashtable里,然后对于每一个b中的值,判断是否在a中存在,因为hashtable查找的平均复杂度为 O(1), 所以,整个算法复杂度为O(N), 但是,这里的空间复杂度为 O(M) 。但是,这种方法适合数组比较小的情况。因为如果a数组比较大,hashtable会出现collision的情况,这样,查找的平均复杂度就不再是 O(1)。

  4. 算法复杂度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;  
}  
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容