Kotlin实现：求解数组最小元素距离

【出自GG面试题】

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

题目描述：

给定一个数组，数组中含有重复元素，给定两个数字num1和num2，求这两个数字在数组中出现的位置的最小距离。

分析与解答：

对于这类问题，最简单的方法就是对数组进行双重遍历，找出最小距离，但是这种方法效率比较低下。由于在求距离的时候只关心num1与num2这两个数，因此，只需要对数组进行一次遍历即可，在遍历的过程中分别记录遍历到num1或num2的位置就可以非常方便地求出最小距离，下面分别详细介绍这两种实现方法。

方法一：蛮力法

主要思路是：对数组进行双重遍历，外层循环遍历查找num1，只要遍历到num1，内层循环对数组从头开始遍历找num2，每当遍历到num2，就计算它们的距离dist。当遍历结束后最小的dist值就是它们最小的距离。实现代码如下：

程序的运行结果如下：

2

算法性能分析：

这种方法需要对数组进行两次遍历，因此，时间复杂度为O（n^2）。

方法二：动态规划(www.xing528.com)

上述方法的内层循环对num2的位置进行了很多次重复的查找。可以采用动态规划的方法把每次遍历的结果都记录下来从而减少遍历次数。具体实现思路是：遍历数组，会遇到以下两种情况：

（1）当遇到num1时，记录下num1值对应的数组下标的位置lastPos1，通过求lastPos1与上次遍历到num2下标的位置的值lastPos2的差可以求出最近一次遍历到的num1与num2的距离。

（2）当遇到num2时，同样记录下它在数组中下标的位置lastPos2，然后通过求lastPos2与上次遍历到num1的下标值lastPos1，求出最近一次遍历到的num1与num2的距离。

假设给定数组为：{4，5，6，4，7，4，6，4，7，8，5，6，4，3，10，8}，num1=4，num2=8。根据以上方法，执行过程如下：

1）在遍历的时候首先会遍历到4，下标为lastPos1=0，由于此时还没有遍历到num2，因此，没必要计算num1与num2的最小距离。

2）接着往下遍历，又遍历到num1=4，更新lastPos1=3。

3）接着往下遍历，又遍历到num1=4，更新lastPos1=7。

4）接着往下遍历，又遍历到num2=8，更新lastPos2=9；此时由于前面已经遍历到过num1，因此，可以求出当前num1与num2的最小距离为|lastPos2-lastPos1|=2。

5）接着往下遍历，又遍历到num2=8，更新lastPos2=15；此时由于前面已经遍历到过num1，因此，可以求出当前num1与num2的最小距离为|lastPos2-lastPos1|=8；由于8＞2，所以，num1与num2的最小距离为2。

实现代码如下：

算法性能分析：

这种方法只需要对数组进行一次遍历，因此，时间复杂度为O（N）。