等值数目问题

问题描述：已知两个整型数组f[]和g[]，它们的元素都已经从小到大排列，并且每个数组中的元素各是各不相同的。例如，f[]中可能是1，3，4，7，9而g[]中可能是3，5，7，8，10。请写一个程序算出这两个数组中有多少组元素是相等的。例如f[2]=g[1]=3,f[4]=g[3]=8,因此上面的例子有两组。

思路：一般情况下，很容易想到下面的方法：

1.固定f[i],检查g[]中的每个元素，看是否有元素与之相等

2.处理f[i+1]的情况

3.循环1，2

这样做肯定是可以解决问题的，但是这么做就没有充分利用到题设的两个重要条件：它们的元素都已经从小到大排列，并且每个数组中的元素各是各不相同的。进一步分析，我们会发现，两个数组中元素比较无外乎三种情况：

1.f[i]>g[j]:f[i]与g[j]不等，并且g[]中不可能有与f[i]相等的元素了，对f[i+1]的比较从j开始；

2.f[i]=g[j]:f[i]与g[j]相等，对f[i+1]的比较从j+1开始；

3.f[i]>g[j]:f[i]与g[j]不等，还有可能找到，因此j++。

下面给出一种实现代码：

#include <stdio.h>/******************************************** *计算两个数组中相同元素的个数 *两个数组都满足如下条件 ********************************************/ int GetSameElementCount(const int a[], int m, const int b[],int n) {     //数组a和b的下标索引     int i,j;     int count = 0;     int yStart = 0;     int num = 0;     for(i = 0; i < m; i++)     {         for(j = yStart; j < n; j++)         {             if(a[i] < b[j])             {                 yStart = j;                 break;             }             else if(a[i] == b[j])             {                 yStart = j + 1;                 count++;                 break;             }         }     }     return count; } int main(void) {     int arr1[] = {1,3,4,7,9};     int arr2[] = {3,5,7,8,10};     int result = GetSameElementCount(arr1,5,arr2,5);     printf("The EQ_COUNT is %d\n",result);     return 0; }

?