2013年1月29日 星期二

[C Programming] 兩陣列最短距離

已知兩個元素自小到大排好的陣列x[]和y[],請寫一個程式,
算出兩個陣列元素彼此之間差的絕對值中最小的一個,這叫作陣列的距離。

解:
跟前面的幾題有異曲同工之妙,
當x[i]比y[j]大的時候就j++,
反之則i++,每次尋找更小的值即可。

Code大概長這樣:
#include <limits.h>

int min(int x, int y)
{
 if(x<y) return x;
 return y;
}

int min_dist(int x[], int y[], int m, int n)
{
 // INT_MAX是limits.h裡的常數,表int的最大值。
 int minimum = INT_MAX, _xi = 0, _yi = 0; 
 while( (_xi < m) && (_yi < n) )
  if(x[_xi] >= y[_yi]) 
  { 
   minimum = min(minimum, x[_xi]-y[_yi]);
   _yi++; 
  }
  else
  { 
   minimum = min(minimum, y[_yi]-x[_xi]);
   _xi++;  
  }   
 return minimum;
}
另外,其實可以加入相等的情況,直接return 0;出來,
但並不一定會比較快,相對還可能每一次迴圈都要判斷兩次。

沒有留言:

張貼留言