问题
给定一个数组，数组中含有重复元素，给定两个元素 num1 和 num2，求它们在数组中出现位置的最小距离。
如数组 [1,3,4,5,2,10,3,1] 中 1 和 4 的最小距离为 2。
解法
常规
常规思路就是使用双重遍历找到两个数的所有位置，计算出最小的一个差值绝对值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func absDiff(a, b int) int {
r := a - b
if r < 0 {
return -r
}
return r
}
// 查找 num1和 num2 在 data 中出现位置的最小距离
func getMinDistance(data []int, num1, num2 int) int {
minDist := math.MaxInt
for idx1, n1 := range data {
if n1 == num1 {
for idx2, n2 := range data {
if n2 == num2 {
dist := absDiff(idx1- idx2)
if dist < minDist {
minDist = dist
}
}
}
}
}
return minDist
}
func main() {
l:=[]int{1,3,4,5,2,10,3,1}
r:=getMinDistance(l,1,4)
// 2
fmt.Println(r)
}
时间复杂度 O(n^2)，空间复杂度 O(1)。
动态规划
上面方法的内存循环，其实进行了很多重复查找，可以用动态规划的方法把每次遍历的结果都记录下来从而减少遍历次数。
遍历数组：
- 当遇到 num1 时，记录下 num1 值对应数组下标的位置 lastPos1，通过求 lastPos1 与上次遍历到的 num2 的下标位置值 lastPos2 的差可以求出最近一次遍历到的 num1 与 num2 的距离。
- 当遇到 num2 时，记录下 num2 值对应数组下标的位置 lastPos2，通过求 lastPos2 与上次遍历到的 num1 的下标位置值 lastPos1 的差可以求出最近一次遍历到的 num1 与 num2 的距离。
每当发生上面情况时，就拿当前得到的距离与已知的最小距离比较下，最后就得到了最小距离。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func min(a, b int) int {
if a <= b {
return a
}
return b
}
func getMinDistance(data []int, num1, num2 int) int {
minDist := math.MaxInt
if len(data) == 0 {
return minDist
}
lastPos1 := -1
lastPos2 := -1
for idx, n := range data {
if n == num1 {
lastPos1 = idx
if lastPos2 > -1 {
minDist = min(minDist, lastPos1-lastPos2)
}
} else if n == num2 {
lastPos2 = idx
if lastPos1 > -1 {
minDist = min(minDist, lastPos2-lastPos1)
}
}
}
return minDist
}
func main() {
l := []int{1, 3, 4, 5, 2, 10, 3, 1}
r := getMinDistance(l, 2, 3)
// 2
fmt.Println(r)
}