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

发布于 2021-09-07 10:42 ，所属分类：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多多。


推荐阅读
涛哥王楠会
涛哥英语配音录
涛哥的深圳租房记
所志在功名，离别何足叹
万 字 攻 略，详 解 腾 讯 面 试
出去之后,好好做人,华为两年,苦乐参半


你好，我是涛哥，CSDN排名第一

自学计算机，毕业后就职华为腾讯

从事软件开发，期待与你一起成长


点击gongzhong号，免费领学习资料
老板，点个“赞”和“在看”呗

相关资源