二路归并法求解两个整型数组的交集

1.问题

已知两个从小到大排好序的整型数组A[8]={1,3,6,8,9,10,12,15};B[6]={1,6,8,13,15,18};则这两个整型数组交集为{1,6,8,15}。

2.当两个数组的长度相当时，可以采用二路归并法来进行求解交集

二路归并法思路：对于数组A,B分别以i,j从头遍历数组。如果当前位置的A[i]等于B[j]，则这两个数是两个数组的一个交集，记录下来并继续遍历；如果A[i]大于B[j]，则继续遍历数组B，否则遍历数组A。算法的代码如下：

int comNum(int a[],int m,int b[],int n,int *p) { //m,n分别为整型数组a,b的长度 int i=0,j=0,cnt=0; while(i<m&&j<n) { if(a[i]==b[j]) { p[cnt++]=a[i]; i++; j++; } else if(a[i]>b[j]) j++; else i++; } return cnt; }

3.算法测试完整程序

//二路归并法 #include<iostream> using namespace std; int comNum(int a[],int m,int b[],int n,int *p) { int i=0,j=0,cnt=0; while(i<m&&j<n) { if(a[i]==b[j]) { p[cnt++]=a[i]; i++; j++; } else if(a[i]>b[j]) j++; else i++; } return cnt; } int main() { int A[8]={1,3,6,8,9,10,12,15},B[6]={1,6,8,13,15,18},i,k; int *count=new int[sizeof(A)/sizeof(int)];//动态内存分配 k=comNum(A,8,B,6,count); for(i=0;i<k;i++) cout<<count[i]<<" "; delete []count;//释放动态内存 return 0; }程序结果：

参考博客：http://blog.csdn.net/jeanphorn/article/details/46392359。