两数组最短距离

两数组最短距离

时间: 1ms        内存:64M

描述:

已知元素从小到大排列的两个数组x[]和y[],请写出一个程序算出两个数组彼此之间差的绝对值中最小的一个,这叫做数组的距离。

输入:

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

输出:

数组的最短距离

示例输入:

5 5
1 2 3 4 5
6 7 8 9 10

示例输出:

1

提示:

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
int main()
{ int f[1000], g[1000]; int m, n, d = INT_MAX; 
int i, j, t;  scanf("%d %d", &m, &n); 
for (i = 0; i < m; ++i) 
 scanf("%d", &f[i]); 
for (i = 0; i < n; ++i)  
scanf("%d", &g[i]);
for (i = 0; i < m; ++i) 
{  for (j = 0; j < n; ++j)  
{   t = abs(f[i] - g[j]);  
 if (t < d)    d = t;  } 
} 
printf("%d\n", d); 
return 0;
}

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

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

  return 0;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注