定义三元组(a,b,c)(其中a,b,c均为正数)的距

第1题

定义三元组(a,b,c)(其中a,b,c均为正数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S₁、S₂和S₃，按升序分别存储在3个数组中。设计一个尽可能高效的算法,计算并输出所有可能的三元组(a,b, c) (a∈S₁, b ∈S₂, c ∈S₃)中的最小距离。例如 S₁={-1,0,9}，S₂ = {-25,-10,10, 11}，S₃ ={2,9,17,30, 41}，则最小距离为2，相应的三元组为(9,10,9)。要求:

1)给出算法的基本设计思想。

2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

3)说明你所设计算法的时间复杂度和空间复杂度。

1)算法的基本设计思想

①使用D_min记录所有已处理过的三元组的最小距离，初值为一个足够大的整数。

② 集合 S₁、S₂和S₃分别保存在数组A、B、C中。数组的下标变量i=j=k=0,当i<|S₁|、j<|S₂|且k <|S₃|时 (|S|表示集合S中的元素个数)，循环执行a)~c)。 

a) 计算 (A[i], B[j], C[k]) 的距离D;(计算D) 

b) 若D<D_min，则D_min=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 =|S₁|+|S₂|+|S₃|，时间复杂度为O(n)，空间复杂度为O(1)。