等值数目

等值数目

时间: 1ms        内存:64M

描述:

已知两个整数数组f[]和g[],它们的元素都已经从小到大排列。例如f[]中可能有 1,2,2,3,3,g[]中有1,2,2,2,3。
请写一个程序,算出这两个数组彼此之间有多少组相同的数据。就以上例而言:
f[0] 于g[0]是第一组;
f[1]于g[1]是第二组;
f[2]于g[2]是第三组;
f[3]于g[4]是第四组。

输入:

第一行为两个整数m, n(1≤m, n≤1000),分别代表数组f[], g[]的长度。
第二行有m个元素,为数组f[]。
第三行有n个元素,为数组g[]。

输出:

输出等值数目。

示例输入:

5 5
1 2 2 2 3
1 2 2 3 3

示例输出:

4

提示:

参考答案(内存最优[748]):

#include"stdio.h"
int main()
{
	int m,n,i,j,d=0;
	int a[1001],b[1001];
	scanf("%d %d",&m,&n);
	for(i=0;i<m;i++)
		scanf("%d",&a[i]);
	for(i=0;i<n;i++)
		scanf("%d",&b[i]);
	i=0;
	j=0;
	while(i<m&&j<n)
	{
		if(a[i]<b[j]) 
			i++;
		else if(a[i]>b[j]) 
			j++;
		else
		{ 
			d++;
			i++; 
			j++;
		}
	}
	
	printf("%d\n",d);
	return 0;
}

参考答案(时间最优[0]):

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>m>>n;
    int i,j;
    int sum=0;
    int a[1002],b[1002];
    for(i=1; i<=m; i++)
        cin>>a[i];
        i=1;
    for(j=1; j<=n; j++)
        {
            cin>>b[j];
            while(a[i]<b[j])
                i++;
            if(i>m)break;

            if(a[i]==b[j])
                {
                    sum++;
                    i++;
                }
        }
    cout<<sum<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞