阿里面试：葡萄的最大值和最小值

 关注

“脚本之家

”，与百万开发者在一起

本文经涛歌依旧（ID：ai_taogeyijiu_2021）授权转载

如若转载请联系原公众号

又到周末，咱们就不聊高深复杂的问题了，来点轻松、愉快、有益的话题。来看看阿里巴巴的一道面试题：

已知数组a[N], 求该数组的最大值和最小值，要求比较次数的数量级是O(1.5n).

求数组的最大值和最小值，居然出现在阿里巴巴的面试中？是不是很搞笑？别忘了，题目中有要求，比较次数的数量级是O(1.5n).

这么说吧，现在的面试都越来越卷了，如果之前完全没有看过类似的问题，那么在面试现场是很难想出解法的，事实就是如此残酷。

所以，无论是社招还是校招，一定要刷题，训练思路。面试的本质是一次考试，跟准备高考一样，没有一定的题量训练就基本歇菜。

涛哥手绘：葡萄也有max和min哦

朴素解法

我们直接来看看朴素解法的思路吧：

• 遍历数组，求出最大值
  

• 遍历数组，求出最小值

显然，此处遍历了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).

既然缕清了思路，那么代码的实现就相对简单了，有兴趣的朋友可以尝试写一下代码。

周末聊了一下简单的问题，祝愿大家面试顺利，在金九银十旗开得胜，offer多多。

  推荐阅读：

每日打卡赢积分兑换书籍入口