题目描述：
已知三个
升序整数数组 a[l], b[m], c[n]，请在三个数组中各找出一个元素，使得组成的三元组距离最小。三元组距离的定义是：假设 a[i], b[j], c[k] 是一个三元组，那么距离为：
Distance=max（| a[i] - b[j] |，| a[i] - c[k]|，| b[j] - c[k] |）。
设计一个求最小三元组距离的最优算法。
方法：
最简单的方法是找出所有可能的组合，从所有可能的组合中找出最小距离，但是效率低下。
通过分析发现，当 a<= b <= c 时，此时它们的距离肯定为 D = c-a，此时就没有必要计算 b-a，c-b了。
- 蛮力法
- 最小距离法
- 数学运算法
1.蛮力法
分别遍历三个数组中的元素，对遍历到的元素分别求出它们的距离，然后按照距离的定义得出最小的距离。
代码实现：
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time : 2020/1/29 19:34
# @Author : buu
# @Software: PyCharm
# @Blog ：https://blog.csdn.net/weixin_44321080
def maxx(a, b, c):
maxs = b if b > a else a
maxs = c if c > maxs else maxs
return maxs
def miDistance(a, b, c):
aLen = len(a)
bLen = len(b)
cLen = len(c)
minDist = maxx(abs(a[0] - b[0]), abs(a[0] - c[0]), abs(b[0] - c[0]))
i = 0
while i < aLen:
j = 0
while j < bLen:
k = 0
while k < cLen:
dist = maxx(abs(a[i] - b[j]), abs(a[i] - c[k]), abs(b[j] - c[k]))
if dist < minDist:
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('min dist:', miDistance(a, b, c))
结果：
算法性能分析：
时间复杂度为O(lmn)；
这种方法没有用到数组升序的特点。
2.最小距离法
假设当前遍历到这三个数组中的元素分别为 ai，bi，ci，且 ai <= bi <= ci，此时它们的距离肯定为 Di = ci - ai；那么接下来分如下三种情况讨论：
(1) 接下来如果求 ai，bi，ci+1 的距离，由于 ci+1 >= ci ，此时它们三元组的距离必为Di+1 = ci+1 - ai，显然 Di+1 >= Di ,所以 Di+1 不可能为最小距离。
(2) 接下来如果求 ai，bi+1，ci+ 的距离，由于 bi <= bi+1 ，
- 若 bi+1 <= ci ，此时它们三元组的距离仍为 Di = ci - ai；
- 若 bi+1 > ci , 此时它们三元组的距离必为Di+1 = bi+1 - ai，显然 Di+1 >= Di ,所以 Di+1 不可能为最小距离。
(3) 如果接下来求 ai+1，bi，ci 的距离，若 Di = | ci - ai | < ci - ai+1 ，此时它们的距离为 max（ci - ai+1，ci - bi），显然 Di+1 < Di ，所以 Di+1 有可能时最小距离。
综上，在求最小距离的时候只需要考虑第三种情况即可。具体实现思路：
从三个数组的第一个元素开始，首先求出它们的距离 minDist ，接着找出这三个数中最小数所在的数组，只对这个数组的下标往后移动一个位置，接着求三个数组中当前遍历元素的距离，如果比 minDist 小，则把当前距离赋值给 minDist ，依此类推，直到遍历完其中一个数组为止。
代码实现：
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time : 2020/1/29 19:49
# @Author : buu
# @Software: PyCharm
# @Blog ：https://blog.csdn.net/weixin_44321080
def maxx(a, b, c):
maxs = b if b > a else a
maxs = c if c > maxs else maxs
return maxs
def minn(a, b, c):
mins = a if a < b else b
mins = c if c < mins else mins
return mins
def minDistance(a, b, c):
aLen = len(a)
bLen = len(b)
cLen = len(c)
minDist = 2 ** 32
minElem = 0
i, j, k = 0, 0, 0
while True:
curDist = maxx(abs(a[i] - b[j]), abs(a[i] - c[k]), abs(b[j] - c[k]))
if curDist < minDist:
minDist = curDist
minElem = minn(a[i], b[j], c[k])
if minElem == a[i]:
i += 1
if i >= aLen:
break
elif minElem == 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('min dist2:', minDistance(a, b, c))
结果：
算法性能分析：
此方法最多只需要对三个数组分别遍历一遍，所以时间复杂度为O(l+m+n)；
end