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

题目描述：

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

方法：

1. 蛮力法
2. 分治法
3. 变形的分治法

1.蛮力法
首先定义两个变量 max 与 min，分别记录数组中最大值与最小值，并将其都初始化为数组的首元素的值，然后从数组的第二个元素开始遍历数组元素，如果遇到的数组元素比max大，则该数组元素的值为当前的最大值，并将该值赋给max；若遇到的数组元素比min小，则该数组元素的值为当前的最小值，并将该值赋给min。

算法性能分析：
最差的情况下比较次数为 2n-2（数组第一个 元素首先赋值给 max 与 min，接下来的 n-1 个元素都需要分别根 max 与 min 比较一次，比较次数为 2n-2），最好的情况下比较次数为n-1，时间复杂度为O(n)；

2.分治法
分治法就是将一个规模为n的、难以直接解决的大问题，分割为k个规模较小的子问题，采取各个击破、分而治之的策略得到各个子问题的解，然后将各个子问题的解进行合并，从而得到原问题的解的一种方法。
本题中，当采用分治法求解时，就是将数组两两一对分组，如果数组元素个数为奇数个，就把最后一个元素单独分为一组，然后分别对每一组中相邻的两个元素进行比较，把二者中值较小的数放在数组的左边，值大的数放在数组的右边，只需要比较n/2次就可以将数组分组完成。然后可以得出结论，最小值一定再每一组的左边部分，最大值一定在每一组的右边部分，接着只需要在每一组的左边部分找最小值，右边部分找最大值，查找分别需要比较n/2-1次和n/2-1次，所以总共的比较次数大约为3n/2-2。

代码实现：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time    : 2020/1/27 14:48
# @Author  : buu
# @Software: PyCharm
# @Blog    ：https://blog.csdn.net/weixin_44321080
class MaxMin:
    def __init__(self):
        self.max = None
        self.min = None

    def getMax(self):
        return self.max

    def getMin(self):
        return self.min

    def getMinandMax(self, arr):
        if arr == None:
            print('参数不合法！')
            return
        i = 0
        lens = len(arr)
        self.max = arr[0]
        self.min = arr[0]
        i = 0
        while i < lens - 1:  # 两两分组，把较小的数放在左半部分
            if arr[i] > arr[i + 1]:
                tmp = arr[i]
                arr[i] = arr[i + 1]
                arr[i + 1] = tmp
            i += 2
        self.min = arr[0]
        i = 2
        while i < lens:  # 在各个分组的左半部分找最小值
            if arr[i] < self.min:
                self.min = arr[i]
            i += 2
        self.max = arr[1]
        i = 3
        while i < lens:  # 在各个分组的右半部分找最大值
            if arr[i] > self.max:
                self.max = arr[i]
            i += 2
        if lens % 2 == 1:  # 如果数组中元素个数是奇数个
            # 最后一个元素被分为一组，单独处理
            if self.max < arr[lens - 1]:
                self.max = arr[lens - 1]
            if self.min > arr[lens - 1]:
                self.min = arr[lens - 1]


if __name__ == '__main__':
    array = [7, 3, 19, 40, 4, 7, 1]
    m = MaxMin()
    m.getMinandMax(array)
    print('max= ' + str(m.max))
    print('min= ' + str(m.min))

结果：

3.变形的分治法
将数组分为左右两个部分，先求出左半部分的最大值和最小值，再求出右半部分的最大值和最小值，然后综合起来，左右两部分的最大值中的较大值即为合并后的较大值，左右两部分的最小值中的较小值即为合并后的较小值，通过此方法即可求得合并后的数组的最大值和最小值。
以上过程是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分的区间内只剩一个元素或两个元素为止。

代码实现：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time    : 2020/1/27 15:07
# @Author  : buu
# @Software: PyCharm
# @Blog    ：https://blog.csdn.net/weixin_44321080
class MaxMin:
    def getMaxandMin(self, array, l, r):
        # 返回值列表中有两个元素，第一个元素为子数组的最小值，第二个元素为最大值
        if array == None:
            print('参数不合法！')
            return
        list = []
        m = (l + r) // 2  # 求中点
        if l == r:  # 某个分组只有一个元素
            max = array[l]
            min = array[r]
            list.append(min)
            list.append(max)
            return list
        if l + 1 == r:
            if array[l] > array[r]:
                max = array[l]
                min = array[r]

            else:  # list中的两个元素，左边小，右边大
                max = array[r]
                min = array[l]
            list.append(min)
            list.append(max)
            return list
        lList = self.getMaxandMin(array, l, m)  # 递归地计算左半部分
        rList = self.getMaxandMin(array, m + 1, r)  # 递归地计算右半部分
        # 总的最大值，最小值
        max = lList[1] if lList[1] > rList[1] else rList[1]
        min = lList[0] if lList[0] < rList[0] else rList[0]
        list.append(min)
        list.append(max)
        return list


if __name__ == '__main__':
    array = [7, 3, 19, 40, 4, 7, 1]
    m = MaxMin()
    result = m.getMaxandMin(array, 0, len(array) - 1)
    print('max= ' + str(result[1]))
    print('min= ' + str(result[0]))

结果：

算法性能分析：
此方法与方法二本质上是相同的，比较次数为3n/2-2。

end