等值数目有关问题

等值数目问题

问题描述：已知两个整型数组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; 
}