document.write('对于这类问题，最简单的方法就是对数组进行双重遍历，找出最小距离，但是这种方法效率比较低下。
由于在求距离的时候只关心num1与num2这两个数，因此，只需要对数组进行一次遍历即可，在遍历
的过程中分别记录遍历到num1或num2的位置就可以非常方便地求出最小距离，下面分别详细介绍这
两种实现方法。
方法一：蛮力法
主要思路为：对数组进行双重遍历，外层循环遍历查找num1，只要遍历到num1，内层循环对数组
从头开始遍历找num2，每当遍历到num2，就计算它们的距离dist。当遍历结束后最小的dist值就是它
们最小的距离。实现代码如下：
def minDistance(arr,num1,num2):
if arr==None or len(arr)＜=0:
print "参数不合理"
return 2**32
minDis=2**32 #num1与num2的最小距离
dist0
i=0
while i＜len(arr):
if arr[i]==num1:
j=0
while j＜len(arr):
if arr[j]==num2:
dist=abs(i-j) #当前遍历的num1与num2的距离
if dist＜minDis:
minDis=dist
j+=1
i+=1
return minDis
if __name__="__main__":
arr=[4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8]
num1=4
num2=8
print minDistance(arr,num1,num2)
程序的运行结果为：
2
算法性能分析：
这种方法需要对数组进行两次遍历，因此，时间复杂度为O(n2
)。
方法二：动态规划
上述方法的内层循环对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。
实现代码如下：
def minDistance(arr,num1,num2):
if arr==None or len(arr)＜=0:
print "参数不合理"
return 2**32
lastPos1=-l# 上次遍历到num1的位置
lastPos2=-1 #上次遍历到num2的位置
minDis=2**30 #num1与num2的最小距离
i=0
while i＜len(arr):
if arr[i]==num1:
lastPos1=i
if lastPos2＞=0:
minDis=min(minDis, lastPos1-lastPos2)
if arr[i]==num2:
IastPos2=i
if lastPos1＞=0:
minDis=min(minDis, lastPos2-lastPos1)
i+=1
return minDis
if __name__=="__main__":
arr=[4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8]
num1=4
num2=8
print minDistance(arr,num1,num2)
算法性能分析：
这种方法只需要对数组进行一次遍历，因此，时间复杂度为O(N)。
');