已知数组a[N], 求该数组的最大值和最小值，要求比较次数的数量级是O(1.5n).
朴素解法
我们直接来看看朴素解法的思路吧：
-
遍历数组，求出最大值
-
遍历数组，求出最小值
显然，此处遍历了2次，时间复杂度是O(2n)，比较的次数也是O(2n)，不符合要求。
优化思路是：直接遍历一次，然后同时求出最大值和最小值。
可是，这就万事大吉了吗？
问题在哪里？虽然时间复杂度是O(n)，但比较次数仍然是O(2n)，不符合题目的要求。
下面，我们来看看如上思路对应的代码：
package main
import "fmt"
func getMinMax(a []int) (int, int){
if len(a) == 0 {
// 异常处理
}
min, max := a[0], a[0]
for _, v := range a {
if v < min {
min = v
}
if v > max {
max = v
}
}
return min, max
}
func main() {
fmt.Println(getMinMax([]int{3, 2, 4, 1, 5, 9, 6, -1}))
}
结果：-1 9
要说明的是，在实际开发工作中，如上程序是能达标的，性能没什么问题，而且可读性极好。
但是，面试就是面试，面试题目就是大家的指挥棒。所以，我们还得按照题目要求进行优化。
优化解法
要进行优化，那就要分析上面朴素解法的不足之处。
上面代码的思路：当遍历前面两个元素后，得到min和max的值分别为2和3，在与接下来的4和1的比较中，min要比较2次， max要比较2次，总共就是4次。
如下图所示：
现在，我们的目标比较次数要优化为O(1.5n)，那该怎么着手去做呢？
我们看到：如果我们先把4和1进行比较，得出较大的4和较小的1, 那么剩下的就只需要将min和1比较，将max和4比较就行，总共比较次数只有3次，减少了无用的比较，如下图：
可以看到，优化的思路就是对元素进行两两分组，比较次数从O(2n)优化到了O(1.5n).
既然缕清了思路，那么代码的实现就相对简单了。
网友评论