document.write('最简单的方法就是找出所有可能的组合，从所有的组合中找出最小的距离，但是显然这种方法的效率比
较低下。通过分析发现，当ai≤bi≤ci时，此时它们的距离肯定为Di=ci-ai。此时就没必要求bi-ai与ci-ai
的值了，从而可以省去很多没必要的步骤，下面分别详细介绍这两种方法。
方法一：蛮力法
最容易想到的方法就是分别遍历三个数组中的元素，对遍历到的元素分别求出它们的距离，然后从这
些值里面查找最小值，实现代码如下：
def maxs(a,b,c):
maxs=b if a＜b else a
maxs=c if maxs＜c else maxs
return maxs
def minDistance(a,b,c):
aLen=len(a)
bLen=len(b)
cLen=len(c)
minDist=maxs(abs(a[0]-b[0]),abs(a[0]-c[0]),abs(b[0]-c[0]))
dist=0
i=0
while i＜aLen:
j=0
while j＜bLen:
k=0
while k＜cLen:
#求距离
dist=maxs(abs(a[i]-b[j]),abs(a[i]-c[k]).abs(b[j]-c[k]))
#找到最小距离
if minDist＞dist:
minDist=dist
k+=1
j+=1
i+=1
return minDist
if __name__=="__main__":
a=[3,4,5,7,15]
b=[10, 12, 14, 16, 17]
c=[20, 21, 23, 24, 37, 30]
print "最小离为: "+str(minDistance(a, b, c))
程序的运行结果为：
最小距离为：5
算法性能分析：
这种方法的时间复杂度为O(l*m*n)，显然这种方法没有用到数组升序这一特性，因此，该方法肯定不
是最好的方法。
方法二：最小距离法
假设当前遍历到这三个数组中的元素分别为ai，bi，ci，并且ai≤bi≤ci，此时它们的距离肯定为Di=ciai，那么接下来可以分如下三种情况讨论：
(1)如果接下来求ai，bi，ci+1的距离，由于ci+1≥ci，此时它们的距离必定为Di+1=ci+1
-ai，显然
Di+1≥Di，因此，Di+1不可能为最小距离。
(2)如果接下来求ai，bi+1，ci的距离，由于bi+1≥bi，如果bi+1≤ci，此时它们的距离仍然为Di+1=ciai；如果bi+1＞ci，那么此时它们的距离为Di+1=bi+1
-ai，显然Di+1≥Di，因此，Di+1不可能为最小距
离。
(3)如果接下来求ai+1，bi，ci的距离，如果ai+1＜ci-|ci-ai
|，此时它们的距离Di+1=max(ci-ai+1，cibi
)，显然Di+1＜Di，因此，Di+1有可能是最小距离。
综上所述，在求最小距离的时候只需要考虑第3种情况即可。具体实现思路为：从三个数组的第一个
元素开始，首先求出它们的距离minDist，接着找出这三个数中最小数所在的数组，只对这个数组的下
标往后移一个位置，接着求三个数组中当前遍历元素的距离，如果比minDist小，则把当前距离赋值给
minDist，依此类推，直到遍历完其中一个数组为止。
例如给定数组：a=[3,4,5,7,15]; b=[10,12,14,16,17]; c=[20,21,23,24,37,30];
1)首先从三个数组中找出第一个元素3,10,20，显然它们的距离为20-3=17；
2)由于3最小，因此，数组a往后移一个位置，求4,10,20的距离为16，由于16＜17，因此，当前数组
的最小距离为16；
3)同理，对数组a后移一个位置，依次类推直到遍历到15的时候，当前遍历到三个数组中的值分别为
15,10,20，最小距离为10；
4)由于10最小，因此，数组b往后移动一个位置遍历12，此时三个数组遍历到的数字分别为
15,12,20，距离为8，当前最小距离是8；
5)由于8最小，数组b往后移动一个位置为14，依然是三个数中最小值，往后移动一个位置为16，当
前的最小距离变为5，由于15是数组a的最后一个数字，因此，遍历结束，求得最小距离为5。
实现代码如下：
def mins(a,b,c):
mins=a if a＜b else b
mins=mins if mins＜c else c
return mins
def maxs(a,b,c):
maxs=b if a＜b else a
maxs=c if maxs＜c else maxs
return maxs
def minDistance(a,b,c):
aLen=len(a)
bLen=len(b)
cLen=len(c)
curDist=0
minsd=0
minDist=2**32
i=0#数组a的下标
j=0#数组b的下标
k=0#数组c的下标
while True:
curDist=maxs(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))
if curDist＜minDist:
minDist=curDist
#找出当前遍历到三个数组中的最小值
minsd=mins(a[i], b[j], c[k])
if minsd=a[i]:
i+=1
if i＞=aLen:
break
elif minsd==b[j]:
j+=1
if j＞=bLen:
break
else:
k+=1
if k＞=cLen:
break
return minDist
if __name__=="__main__":
a=[3,4,5,7,15]
b=[10, 12, 14, 16, 17]
c=[20, 21, 23, 24, 37, 30]
print "最小距离为: "+str(minDistance(a,b,c))
算法性能分析：
采用这种算法最多只需要对三个数组分别遍历一遍，因此，时间复杂度为O(1+n1+n)。
方法三：数学运算法
采用数学方法对目标函数变形，有两个关键点，第一个关键点：
max {|x1-x2|,|y1-y2|}=(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 (公式1)
我们假设x1=a[i]，x2=b[j]，x3=c[k]，则
Distance=max(|x1-x2|,|x1-x3|,|x2-x3|)=max(max(|x1-x2|,|x1-x3|),|x2-x3|) (公式2)
根据公式1，max(|x1-x2|，|x1-x3|)=1/2(|2x1-x2-x3|+|x2-x3|)，带入公式2，得到
Distance=max(1/2(|2x1-x2-x3|+|x2-x3|),|x2-x3|)=1/2*max(|2×1-x2-x3|,|x2-x3|)+1/2*|x2-x3|//
把相同部分1/2*|x2-x3|分离出来
=1/2*max(|2x1-(x2+x3)|,|x2-x3|)+1/2*|x2-x3|//把(x2+x3)看成一个整体，使用公式1
=1/2*1/2*((|2x1-2x2|+|2x1-2x3|)+1/2*|x2-x3|
=1/2*|x1-x2|+1/2*|x1-x3|+1/2*|x2-x3|
=1/2*(|x1-x2|+|x1-x3|+|x2-x3|)//求出等价公式，完毕!
第二个关键点：如何设计算法找到(|x1-x2|+|x1-x3|+|x2-x3|)的最小值，x1，x2，x3，分别是三个数
组中的任意一个数，算法思想与方法二相同，用三个下标分别指向a，b，c中最小的数，计算一次它们
最大距离的Distance，然后再移动三个数中较小的数组的下标，再计算一次，每次移动一个，直到其中
一个数组结束为止。
示例代码如下：
def mins(a,b,c):
mins=a if a＜b elseb
mins=mins if mins＜c else c
return mins
def minDistance(a,b,c):
aLen=len(a)
bLen=len(b)
cLen=len(c)
MinSum=0# 最小的绝对值和
Sum=0#计算三个绝对值的和, 与最小值做比较
MinOFabc=0 # a[i], b[j], c[k]的最小值
cnt=0# 循环次数统计, 最多是1+m+n次i=0, j=0, k=0//a,b,c三个数组的下标索引
i=j=k=0
MinSum=(abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]))/2
cnt=0
while cnt＜=aLen+bLen+cLen:
Sum=(abs(a[i]-b[j])+abs(a[i]-c[k])+abs(b[j]-c[k]))/2
MinSum=MinSum if MinSum＜Sum else Sum
MinOFabc=mins(a[i], b[j], c[k])# 找到a[i],b[j],c[k]的最小值
#判断哪个是最小值, 做相应的索引移动
if MinOFabc==a[i]:
i+=1
if i＞=aLen:
break # a[i]最小, 移动i
if MinOFabc==b[j]:
j+=1
if j＞=bLen:
break #b[j]最小, 移动j
if MinOFabc==c[k]:
k+=1
if k＞=cLen:
break #c[k]最小, 移动k
cnt+=1
return MinSum
if __name__=="__main__":
a=[3,4,5,7,15]
b=[10,12,14,16,17]
c=[20,21,23,24,37,30]
print "最小距离为: "+str(minDistance(a, b, c))
程序的运行结果为：
最小距离为：5
算法性能分析：
与方法二类似，这种方法最多需要执行(1+m+n)次循环，因此，时间复杂度为O(1+m+n)。
');