4.2python如何查找数组中元素的最大值和最小值
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了4.2python如何查找数组中元素的最大值和最小值，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4036字，纯文字阅读大概需要6分钟。
内容图文
题目描述：
给定数组a1，a2，…，an，要求找出数组中的最大值和最小值。假设数组中的值两两各不相同。
方法：
- 蛮力法
- 分治法
- 变形的分治法
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
布欧不欧 发布了70 篇原创文章 · 获赞 2 · 访问量 2262 私信 关注内容总结
以上是互联网集市为您收集整理的4.2python如何查找数组中元素的最大值和最小值全部内容，希望文章能够帮你解决4.2python如何查找数组中元素的最大值和最小值所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。