利用分治法求解查找最大和最小元素 c++实现
时间: 2024-01-18 20:03:15 浏览: 35
下面是利用分治法求解查找最大和最小元素的 C++ 实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 分治查找最大和最小元素
pair<int, int> findMaxAndMin(vector<int>& nums, int left, int right) {
// 只有一个元素
if (left == right) {
return make_pair(nums[left], nums[left]);
}
// 只有两个元素
if (left + 1 == right) {
return make_pair(min(nums[left], nums[right]), max(nums[left], nums[right]));
}
// 分治查找左右子区间的最大和最小元素
int mid = (left + right) / 2;
auto leftPair = findMaxAndMin(nums, left, mid);
auto rightPair = findMaxAndMin(nums, mid + 1, right);
// 合并得到整个区间的最大和最小元素
return make_pair(min(leftPair.first, rightPair.first), max(leftPair.second, rightPair.second));
}
int main() {
vector<int> nums = { 3, 1, 4, 2, 5 };
int n = nums.size();
auto result = findMaxAndMin(nums, 0, n - 1);
cout << "最小值:" << result.first << endl;
cout << "最大值:" << result.second << endl;
return 0;
}
```
其中,`findMaxAndMin` 函数采用递归的方式进行分治,首先判断区间内是否只有一个元素或两个元素,再分别递归查找左右子区间的最大和最小元素,最后将左右子区间的结果进行合并得到整个区间的最大和最小元素。实现过程中,使用 `pair` 类型来同时返回最大和最小元素,方便输出结果。在 `main` 函数中,调用 `findMaxAndMin` 函数并输出最大和最小元素的结果。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)