Kotlin 面试算法：数组最大值、最小值及查找技巧

4.2 如何查找数组中元素的最大值和最小值

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

题目描述

给定数组 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 个规模较小的子问题，采取各个击破、分而治之的策略得到各个子问题的解，然后将各个子问题的解进行合并，从而得到原问题的解的一种方法。

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

实现代码如下：

class MaxMin {
    var max: Int = 0 private set
    var min: Int = 0 private set

    fun getMaxAndMin(arr: IntArray?) {
        if (arr == null) {
            println("参数不合法")
            return
        }
        var i = 0
        val len = arr.size
        max = arr[0]
        min = arr[0]
        // 两两分组，把较小的数放到左半部分，较大的数放到右半部分
        i = 
         (i < len - ) {
             (arr[i] > arr[i + ]) {
                 tmp = arr[i]
                arr[i] = arr[i + ]
                arr[i + ] = tmp
            }
            i += 
        }
        
        min = arr[]
        i = 
         (i < len) {
             (arr[i] < min) {
                min = arr[i]
            }
            i += 
        }
        
        max = arr[]
        i = 
         (i < len) {
             (arr[i] > max) {
                max = arr[i]
            }
            i += 
        }
        
         (len %  == ) {
             (max < arr[len - ]) max = arr[len - ]
             (min > arr[len - ]) min = arr[len - ]
        }
    }
}

 {
     array = intArrayOf(, , , , , , )
     m = MaxMin()
    m.getMaxAndMin(array)
    println()
    println()
}