Kotlin程序员查找数组元素最大最小值

【出自GG面试题】

难度系数：★★★☆☆ 被考察系数：★★★★☆

题目描述：

给定数组a1，a2，a3，…an，要求找出数组中的最大值和最小值。假设数组中的值两两各不相同。

分析与解答：

虽然题目没有时间复杂度与空间复杂度的要求，但是给出的算法的时间复杂度肯定是越低越好。

方法一：蛮力法

查找数组中元素的最大值与最小值并非是一件困难的事情，最容易想到的方法就是蛮力法。具体过程如下：首先定义两个变量max与min，分别记录数组中最大值与最小值，并将其都初始化为数组的首元素的值，然后从数组的第二个元素开始遍历数组元素，如果遇到的数组元素的值比max大，则该数组元素的值为当前的最大值，并将该值赋给max，如果遇到的数组元素的值比min小，则该数组元素的值为当前的最小值，并将该值赋给min。

算法性能分析：

上述方法的时间复杂度为O（n），但很显然，以上这种方法称不上是最优算法，因为最差情况下比较的次数达到了2n-2次（数组第一个元素首先赋值给max与min，接下来的n-1个元素都需要分别跟max与min比较一次，一次比较次数为2n-2），最好的情况下比较次数为n-1。是否可以将比较次数降低呢？回答是肯定的，分治法就是一种高效的方法。

方法二：分治法

分治法就是将一个规模为n的、难以直接解决的大问题，分割为k个规模较小的子问题，采取各个击破、分而治之的策略得到各个子问题的解，然后将各个子问题的解进行合并，从而得到原问题的解的一种方法。(www.xing528.com)

本题中，当采用分治法求解时，就是将数组两两一对分组，如果数组元素个数为奇数个，就把最后一个元素单独分为一组，然后分别对每一组中相邻的两个元数进行比较，把两者中值小的数放在数组的左边，值大的数放在数组右边，只需要比较n/2次就可以将数组分组完成。然后可以得出结论：最小值一定在每一组的左边部分，最大值一定在每一组的右边部分，接着只需要在每一组的左边部分找最小值，右边部分找最大值，查找分别需要比较n/2-1次和n/2-1次。因此，总共比较的次数大约为n/2×3=3n/2-2次。

实现代码如下：

程序的运行结果如下：

max=40

min=1

方法三：变形的分治法

除了以上所示的分治法以外，还有一种分治法的变形，其具体步骤如下：将数组分成左右两部分，先求出左半部分的最大值和最小值，再求出右半部分的最大值和最小值，然后综合起来，左右两部分的最大值中的较大值即为合并后的数组的最大值，左右两部分的最小值中的较小值即为合并后的数组的最小值，通过此种方法即可求合并后的数组的最大值与最小值。

以上过程是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素为止。

示例代码如下：

算法性能分析：

这种方法与方法二的思路从本质上讲是相同的，只不过这种方法是使用递归的方式实现的，因此，比较次数为3n/2-2。