第41题
定义三元组(a,b,c)(其中a,b,c均为正数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。设计一个尽可能高效的算法,计算并输出所有可能的三元组(a,b, c) (a∈S1, b ∈S2, c ∈S3)中的最小距离。例如 S1={-1,0,9}，S2 = {-25,-10,10, 11}，S3 ={2,9,17,30, 41}，则最小距离为2，相应的三元组为(9,10,9)。要求:
1)给出算法的基本设计思想。
2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。
1)算法的基本设计思想
①使用Dmin记录所有已处理过的三元组的最小距离，初值为一个足够大的整数。
② 集合 S1、S₂和S3分别保存在数组A、B、C中。数组的下标变量i=j=k=0,当i<|S1|、j<|S₂|且k <|S3|时 (|S|表示集合S中的元素个数)，循环执行a)~c)。
a) 计算 (A[i], B[j], C[k]) 的距离D;(计算D)
b) 若D<Dmin，则Dmin=D;(更新D)
c) 将 A[i], B[j], C[k]中的最小值的下标+1;(对照分析:最小值为a，最大值为c，这里c不变而更新a，试图寻找更小距离D)
③ 输出Dmin，结束。
2)算法实现:
#define INT MAX 0x7fffffff
int abs_(int a) {//计算绝对值
if(a<0) return -a;
else return a;
}
bool xls min(int a,int b,int c){//a是否是三个数中的最小值
if(a<=b&&a<=c) return true;
return false;
}
int findMinofTrip(int A[l,int n,int B[],int m,int C[], int p){
//D min用于记录三元组的最小距离，初值赋为INTMAX
int i=0,j=0,k=0,D min=INT MAX,D;
while(i<n&&j<m&&k<p&&D_min>0){
D=abs_(A[i]-B[j])+abs_(B[j]-C[k])+abs_(C[k]-A[i]);//计算D
if(D<D_min) D_min=D; //更新D
if(xls_min(A[i],B[j],C[k])) i++; //更新a
else if(xls_min(B[j],C[k],A[i]))j++;
else k++;
}
return D_min;
3) 设n =|S1|+|S₂|+|S₃|，时间复杂度为O(n)，空间复杂度为O(1)。