python利用分治法求一组数据中最大的两个数和最小的两个数。函数输入三个数,分别是数组的第一个数,数组长度与数组的最后一个数
时间: 2024-11-20 13:39:12 浏览: 45
分治法是一种将问题分解成更小的子问题,分别解决这些子问题,然后将结果合并以得到原问题的解的方法。在这个问题中,我们可以使用分治法来找到数组中最大的两个数和最小的两个数。
首先,我们定义一个函数,输入参数为数组的第一个元素、数组长度和数组的最后一个元素。然后,我们将数组分成两部分,递归地在每部分中找到最大的两个数和最小的两个数。最后,我们将这两部分的结果合并,得到整个数组的最大两个数和最小两个数。
下面是Python代码实现:
```python
def find_two_largest_smallest(arr, start, end):
if end - start == 1: # 只有两个元素
if arr[start] > arr[end]:
return (arr[start], arr[end]), (arr[end], arr[start])
else:
return (arr[end], arr[start]), (arr[start], arr[end])
elif end - start == 0: # 只有一个元素
return (arr[start], None), (arr[start], None)
else:
mid = (start + end) // 2
left_max, left_min = find_two_largest_smallest(arr, start, mid)
right_max, right_min = find_two_largest_smallest(arr, mid+1, end)
# 合并左右两边的结果
overall_max = sorted([left_max[0], right_max[0]], reverse=True)[:2]
overall_min = sorted([left_min[0], right_min[0]])[:2]
return (overall_max[0], overall_max[1]), (overall_min[0], overall_min[1])
# 示例
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
first_element = arr[0]
last_element = arr[-1]
length = len(arr)
result = find_two_largest_smallest(arr, 0, length - 1)
print("最大的两个数:", result[0])
print("最小的两个数:", result[1])
```
这段代码首先检查数组的长度,如果长度为1或2,直接返回相应的最大值和最小值。如果长度大于2,则将数组分为两部分,递归地找出每部分的最大两个数和最小两个数,然后将结果合并。最终输出整个数组的最大两个数和最小两个数。
阅读全文
相关推荐


















