Python ---- 算法入门(2)分治算法解决【找数组的最大值和最小值】问题
2023-09-14 09:15:07 时间
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_max
4.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. 执行结果
WXRUI体验二维码
下载
相关文章
- Python一键生成国庆渐变头像
- SPC(Statistical Process Control 统计过程控制)图——Python+JS实现
- python字符串转化列表_Python列表到字符串的转换[通俗易懂]
- Word2vec原理及其Python实现「建议收藏」
- python基础之五大标准数据类型
- 符合python命名规范的标识符是什么_Python标识符命名规范
- python常见运维脚本_Python运维常用脚本[通俗易懂]
- 《python数据分析与数据化运营》笔记2021.9.16
- 【说站】如何用python绘制彩色蟒蛇
- python图像多层小波分解_Python中图像小波分解与重构以及灰度图加噪
- Python冒泡排序算法及其优化「建议收藏」
- 数据结构与算法Python_数据结构与算法python语言实现
- python自动化测试—Python自动化框架及工具
- 强化学习技巧三:Python多进程
- Python进阶之递归算法详解
- 使用python-jenkins管理Jenkins
- 改进的自适应中值滤波算法 去除椒盐噪声 python 代码实现
- Python面向对象编程-类和对象-类的定义和使用(三)
- python获得本机本地ip地址的方法汇总详解编程语言
- Python 算法(2) 哈夫曼编码 Huffman Encoding详解编程语言
- 使用Python编程连接MySQL数据库(python连mysql)
- 提升Linux环境:升级Python(linux升级python)
- python使用Python轻松操作Redis(redis-)
- Python实现Oracle数据库连接(python连接oracle数据库)
- python实现k均值算法示例(k均值聚类算法)
- Python生成pdf文件的方法