【正确答案】
【答案解析】问题描述：已知3个升序整数数组a[1]、b[m]和c[n]。请在3个数组中各找一个元素，使得组成的三元组距离最小。三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为Distance=max(|a[i]-b[j]|，|a[i]-c[k]|，|b[j]-c[k]|)，请设计一个求最小三元组距离的最优算法。
方法一：“蛮力”法。最容易想到的方法就是分别遍历3个数组中的元素，分别求出它们的距离，然后从这些值里面查找最小值，示例如下：
public class Test{
public static int max(int a, int b, int c){
int max=a＜b?b:a;
max=max＜c?c:max;
return max;
}
public static int Solvingviolence(int a[], int b[], int c[]){
int aLen=a.length;
int bLen=b.length;
int cLen=c.length;
int minDist=max(Math.abs(a[0]-b[0]), Math.abs(a[0]-c[0]), Math.abs(b[0]-
c[0]));
int dist=0;
for(int i=0; i＜aLen; i++){
for(int j=0; j＜bLen; j++){
for(int k=0; k＜cLen; k++){
//求距离
dist=max(Math.abs(a[i]-b[j]), Math.abs(a[i]-c[k]),
Math.abs(b[j]-c[k]));
//找出最小距离
if(minDist＞dist){
minDist=dist;
}
}
}
}
return minDist;
}
public static void main(String[]args){
int a[]={3, 4, 5, 7};
int b[]={10, 12, 14, 1, 5, 17};
int c[]={20, 21, 23, 24, 37, 30};
System.out.println(Solvingviolence(a, b, c));
}
}
这个算法的时间复杂度为O(1*m*n)，显然这个方法没有用到数组升序这一特性，因此不是最好的方法。
方法二：最小距离法。假设当前遍历到这3个数组中的元素分别为a
i
，b
i
，c
i
，并且a
i
＜=b
i
＜=c
i
，此时它们的距离肯定为D
i
=c
i
-a
i
，那么可以分如下3种情况讨论：
1)如果接下来求a
i
，b
i
，c
i+1
的距离，那么由于c
i+1
＞=c
i
，此时它们的距离必定为D
i+1
=c
i+1
-a
i
，显然D
i+1
＞=D
i
，因此D
i+1
不可能为最小距离。
2)如果接下来求a
i
，b
i+1
，c
i
的距离，由于b
i+1
＞=b
i
，如果b
i+1
＜=c
i
，此时它们的距离仍然为D
i+1
=c
i
-a
i
；如果b
i+1
＞c
i
，那么此时它们的距离为D
i+1
=b
i+1
-a
i
，显然D
i+1
＞=D
i
，因此D
i+1
不可能为最小距离。
3)如果接下来求a
i+1
，b
i
，c
i
的距离，如果a
i+1
＜|c
i
-a
i
|+c
i
，此时它们的距离D
i+1
=c
i
-a
i+1
，显然D
i+1
＜D
i
，因此D
i+1
有可能是最小距离。
综上所述，在求最小距离时只需要考虑第3种情况。具体实现思路为：从3个数组的第一个元素开始，先求出它们的距离minDist，接着找出这3个数中最小数对应的数组，只对这个数组的下标往后移一个位置，接着求3个数组中当前元素的距离，若比minDist小，则把当前距离赋值给minDist，以此类推，直到遍历完其中一个数组。实现代码如下：
public class Test{
public static int min(int a, int b, int c){
int min=a＜b?a:b;
min=min＜c?min:c;
return min;
}
public static int max(int a, int b, int c){
int max=a＜b?b:a;
max=max＜c?c:max;
return max;
}
public static int minDistance(int a[], int b[], int c[]){
int aLen=a.length;
int bLen=b.length;
int cLen=c.length;
int eurDist=0;
int min=0;
int minDist=Integer.MAX_VALUE;
int i=0;//数组a的下标
int j=0;//数组b的下标
int k=0;//数组c的下标
while(true){
curDist=max(Math.abs(a[i]-b[j]), Math.abs(a[i]-c[k]), Math.abs(b[j]-c[k]));
if(curDist＜minDist)
minDist=curDist;
//找出当前遍历到3个数组中的最小值
min=min(a[i], b[j], c[k]);
if(min==a[i]){
if(++i＞=aLen)
break;
}
else if(min==b[j]){
if(++j＞=bLen)
break;
}
else{
if(++k＞=cLen)
break;
}
}
return minDist;
}
public static void main(String[]args){
int a[]={3, 4, 5, 7};
int b[]={10, 12, 14, 16, 17};
int c[]={20, 21, 23, 24, 37, 30};
System.out.println(minDistance(a, b, c));
}
}
采用这种算法最多只需对3个数组分别遍历一遍，因此时间复杂度为O(1+m+n)。