Kotlin程序员求解最小三元组距离

【出自GG面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

已知三个升序整数数组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_i≤b_i≤c_i时，此时它们的距离肯定为D_i=c_i-a_i。此时就没必要求b_i-a_i与c_i-ai的值了，从而可以省去很多不必要的步骤，下面分别详细介绍这两种方法。

方法一：蛮力法

最容易想到的方法就是分别遍历三个数组中的元素，对遍历到的元素分别求出它们的距离，然后从这些值里面查找最小值，实现代码如下：

程序的运行结果如下：

最小距离为：5

算法性能分析：

这种方法的时间复杂度为O（l*m*n），显然这种方法没有用到数组升序这一特性，因此，该方法肯定不是最好的方法。

方法二：最小距离法

假设当前遍历到这三个数组中的元素分别为a_i、b_i和c_i，并且a_i≤b_i≤c_i，此时它们的距离肯定为D_i=c_i-a_i，那么接下来可以分如下三种情况讨论：

（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-|c_i-a_i|，此时它们的距离D_i+1=max（c_i-a_i+1，c_i-b_i），显然D_i+1＜D_i，因此，D_i+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。(www.xing528.com)

5）由于8最小，数组b往后移动一个位置为14，依然是三个数中最小值，往后移动一个位置为16，当前的最小距离变为5，由于15是数组a的最后一个数字，因此，遍历结束，求得最小距离为5。

实现代码如下：

算法性能分析：

采用这种算法最多只需要对三个数组分别遍历一遍，因此，时间复杂度为O（l+m+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（|2x1-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，然后再移动三个数中较小的数组的下标，再计算一次，每次移动一个，直到其中一个数组结束为止。

示例代码如下：

程序的运行结果如下：

最小距离为：5

算法性能分析：

与方法二类似，这种方法最多需要执行（l+m+n）次循环，因此，时间复杂度为O（l+m+n）。