Python ---- 算法入门(2)分治算法解决【找数组的最大值和最小值】问题
Python ---- 算法入门(2)分治算法解决【找数组的最大值和最小值】问题
Rattenking
发布于 2022-08-26 14:51:01
发布于 2022-08-26 14:51:01
文章被收录于专栏：Rattenking
1. 题目
查找数组（序列）中最大值或最小值的算法有很多，接下来我们以 [12,16,7,9,8] 序列为例讲解两种查找最值的算法。
2. 分治算法
分治算法解决问题的思路是：先将整个问题拆分成多个相互独立且数据量更少的小问题，通过逐一解决这些简单的小问题，最终找到解决整个问题的方案。
3. 普通循环对比获取最大值和最小值
- 如果列表没有值，直接返回-1；
- 将列表中的第一个值赋值给min和max，默认最大和最小；
- 循环列表，获取当前值和min或max进行对比；
- 当 min > cur_value，更新 min = cur_value；
- 当 max < cur_value，更新 max = cur_value；
- 循环完成，返回min和max。
# 通过对比获取最大或最小值
def get_max_and_min(arr):
if len(arr) == 0:
return - 1
min = arr[0]
max = arr[0]
for i in range(1,len(arr)):
cur_value = arr[i]
if min > cur_value:
min = cur_value
if max < cur_value:
max = cur_value
return { 'min': min, 'max': max }4. 分治算法获取最大值
4.1 代码分析
- 如果列表长度是0，直接返回-1，表示没找到最大值；
- 当分区只有2个值时，获取其中最大的返回
- 将列表分割成两个区域；
- 获取列表的中间位置index；
- 递归回调，获取左边列表的最大值；
- 递归回调，获取右边列表的最大值；
- 注意：此处切割，会将列表不断的分，直到列表中只存在一个或两个元素时，获取最大的返回，然后再左边和右边比较，返回最大值。
# 通过分治法获取列表中的最大值
def get_max(arr, left, right):
# 如果列表长度是0，直接返回-1，表示没找到最大值
if len(arr) == 0:
return - 1
# 当分区只有2个值时，获取其中最大的返回
if right - left <= 1:
if arr[left] >= arr[right]:
return arr[left]
return arr[right]
return get_split_two_area_max(arr, left, right)
def get_split_two_area_max(arr, left, right):
# 计算列表的中间值,将列表等分为两个区域
middle = int((left + right) / 2 + left)
left_max = get_max(arr, left, middle)
right_max = get_max(arr, middle + 1, right)
if left_max >= right_max:
return left_max
else:
return right_max4.2 注意：列表元素超过5，会导致递归报错！
RecursionError: maximum recursion depth exceeded while calling a Python object
5. 分治算法获取最小值
5.1 求最小值代码分析
- 如果列表长度是0，直接返回-1，表示没找到最小值；
- 当分区只有2个值时，获取其中最小的返回
- 将列表分割成两个区域；
- 获取列表的中间位置index；
- 递归回调，获取左边列表的最小值；
- 递归回调，获取右边列表的最小值；
- 注意：此处切割，会将列表不断的分，直到列表中只存在一个或两个元素时，获取最小的返回，然后再左边和右边比较，返回最小值。
# 通过分治算法，获取列表中的最小值
def get_min(arr, left, right):
if len(arr) == 0:
return -1
if right - left <= 1:
if arr[left] <= arr[right]:
return arr[left]
return arr[right]
mid = int((left + right) / 2 + left)
min_left = get_min(arr, left, mid)
min_right = get_min(arr, mid + 1, right)
if min_left <= min_right:
return min_left
else:
return min_right 5.2 注意：列表元素超过5，会导致递归报错！
RecursionError: maximum recursion depth exceeded while calling a Python object
6. 完整代码
'''
Descripttion:
version: 1.0.0
Author: Rattenking
Date: 2022-07-12 16:16:48
LastEditors: Rattenking
'''
# 通过分治法获取列表中的最大值
def get_max(arr, left, right):
# 如果列表长度是0，直接返回-1，表示没找到最大值
if len(arr) == 0:
return - 1
# 当分区只有2个值时，获取其中最大的返回
if right - left <= 1:
if arr[left] >= arr[right]:
return arr[left]
return arr[right]
return get_split_two_area_max(arr, left, right)
def get_split_two_area_max(arr, left, right):
# 计算列表的中间值,将列表等分为两个区域
middle = int((left + right) / 2 + left)
left_max = get_max(arr, left, middle)
right_max = get_max(arr, middle + 1, right)
if left_max >= right_max:
return left_max
else:
return right_max
# 通过分治算法，获取列表中的最小值
def get_min(arr, left, right):
if len(arr) == 0:
return -1
if right - left <= 1:
if arr[left] <= arr[right]:
return arr[left]
return arr[right]
mid = int((left + right) / 2 + left)
min_left = get_min(arr, left, mid)
min_right = get_min(arr, mid + 1, right)
if min_left <= min_right:
return min_left
else:
return min_right
# 通过对比获取最大或最小值
def get_max_and_min(arr):
if len(arr) == 0:
return - 1
min = arr[0]
max = arr[0]
for i in range(1,len(arr)):
cur_value = arr[i]
if min > cur_value:
min = cur_value
if max < cur_value:
max = cur_value
return { 'min': min, 'max': max }
if __name__ == '__main__':
lists = [12,16,7,9,8]
max = get_max(lists, 0, len(lists) - 1)
print("最大值：", max)
min = get_min(lists, 0, len(lists) - 1)
print("最小值：", min)
# 通过对比获取列表中的最大值和最小值
min_and_max = get_max_and_min(lists)
print("最大值：", min_and_max['max'])
print("最小值：", min_and_max['min'])7. 执行结果
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-07-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
