C或C++ 求两个数组相同元素个数

C或C++ 求两个数组相同元素个数

方法一：查找一个数组里面最小和次小的两个元素，可采用先按从小到大排序，然后，取出前两位数，得到最小和次小。但这种方法时间复杂度较高。
方法二：

先假定数组的前两位中的较小的是最小，较大的是次小
循环检查其余的元素，

若新元素小于最小，则，最小变为次小，新元素成为最小
否则，再判断新元素是否小于次小，是，则新元素变为次小

循环结束，输出两个数。

这种方法，一次遍历数组，就可以得到结果，效率比排序高出很多。
参考代码及运行效果：

我也不会做，我觉得用两个for循环，
for(i=0;f[i]!='\0';i++)
for(j=0;f[j]!='\0';j++)
{if(f[i]=f[j])
n++}
思路就这样，自己写吧

用2分查找
nlgn

#include

int BSearch(int a[], int l, int r, int v)
{
if (l <= r)
{
int m = (l + r) / 2;

if (a[m] == v)
{
return m;
}
else if (a[m] < v)
{
BSearch(a, l + 1, r, v);
}
else
{
BSearch(a, l, r - 1, v);
}
}
else
return -1;
}

int main()
{
int f[4]={1,3,4,7}, g[5]={2,3,5,7,8}, int n = 0;
for (int i = 0; i < 5; i++)
{
if (BSearch(f, 0, 4, g[i]) != -1)
{
printf("%d\n", g[i]);
}
}
return 0;
}

#include
int Match2Array(const int * pArray1 , int iSize1 , const int * pArray2 , int iSize2 )
{
const int * piFirEnd = pArray1+iSize1 , *piSecEnd = pArray2+iSize2;
int iRet = 0;

while ( pArray1 < piFirEnd && pArray2 < piSecEnd )
{
if ( *pArray1 == *pArray2)
{
printf("%d ", *pArray1);

pArray1++;
pArray2++;
iRet++;
}
else if ( *pArray1 < *pArray2 )
{
pArray1++;
}
else
{
pArray2++;
}
}

return iRet;
}

#define ARRAYSIZE(array) ( sizeof(array)/sizeof(array[0]) )
int main(void )
{
int f[]={1,3,4,7,9,11,23};
int g[]={2,3,5,7,8,9,10,23};

int i = Match2Array( f , ARRAYSIZE(f) , g ,ARRAYSIZE(g));

getch();

}

时间复杂度o(m+n),m，n分别为两个数组大小.即最大比较次数为两个数组大小之和.

假如当前位置两个相等，则加1，元素互不相同，且有序，则第二个数组中不会再有其他数和第一个数组中当前数相同，故第一个数组当前位置加1，同理，第二个数组当前位置加1.

假如第一个数组元素小于第二个数组元素(*pArray1 < *pArray2 ),数组二中不会再有元素等于*pArray1，但是数组一可能还有元素等于*pArray2 。故pArray1++。

第一个数组元素大于第二个数组元素(*pArray1 < *pArray2 ),同理于第二种情况。

如有疑问，百度hi