Python ---- 算法入门(2)分治算法解决【找数组的最大值和最小值】问题_python分治算法题目

1. 题目

查找数组（序列）中最大值或最小值的算法有很多，接下来我们以 [12,16,7,9,8] 序列为例讲解两种查找最值的算法。

2. 分治算法

分治算法解决问题的思路是：先将整个问题拆分成多个相互独立且数据量更少的小问题，通过逐一解决这些简单的小问题，最终找到解决整个问题的方案。

3. 普通循环对比获取最大值和最小值

1. 如果列表没有值，直接返回-1；
2. 将列表中的第一个值赋值给min和max，默认最大和最小；
3. 循环列表，获取当前值和min或max进行对比；
4. 当 min > cur_value，更新 min = cur_value；
5. 当 max < cur_value，更新 max = cur_value；
6. 循环完成，返回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 }
1
2
3
4
5
6
7
8
9
10
11
12
13

4. 分治算法获取最大值

4.1 代码分析

1. 如果列表长度是0，直接返回-1，表示没找到最大值；
2. 当分区只有2个值时，获取其中最大的返回
3. 将列表分割成两个区域；
4. 获取列表的中间位置index；
5. 递归回调，获取左边列表的最大值；
6. 递归回调，获取右边列表的最大值；
7. 注意：此处切割，会将列表不断的分，直到列表中只存在一个或两个元素时，获取最大的返回，然后再左边和右边比较，返回最大值。

# 通过分治法获取列表中的最大值
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4.2 注意：列表元素超过5，会导致递归报错！

RecursionError: maximum recursion depth exceeded while calling a Python object

5. 分治算法获取最小值

5.1 求最小值代码分析

1. 如果列表长度是0，直接返回-1，表示没找到最小值；
2. 当分区只有2个值时，获取其中最小的返回
3. 将列表分割成两个区域；
4. 获取列表的中间位置index；
5. 递归回调，获取左边列表的最小值；
6. 递归回调，获取右边列表的最小值；
7. 注意：此处切割，会将列表不断的分，直到列表中只存在一个或两个元素时，获取最小的返回，然后再左边和右边比较，返回最小值。

# 通过分治算法，获取列表中的最小值
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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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'])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

7. 执行结果

WXRUI体验二维码

下载

我的博客，欢迎交流！

我的CSDN博客，欢迎交流！

微信小程序专栏

前端笔记专栏

微信小程序实现部分高德地图功能的DEMO下载

微信小程序实现MUI的部分效果的DEMO下载

微信小程序实现MUI的GIT项目地址

微信小程序实例列表

前端笔记列表

游戏列表