看似简单的姐数组中的最大值实际上体现了不同的思路本文将以比较数组大小为背景，分别展示普通算法和分治法，通过对比来简述分治法。
问题描述
给定一个整数数组，编写一个算法来找到数组中的最大值和最小值。
解决方法
方法一：遍历数组
最简单的方法是遍历数组并比较每个元素，找到最大值和最小值。
#include <iostream>
#include <vector>
using namespace std;
void findMinMax(vector<int>& nums, int& minVal, int& maxVal) {
if (nums.empty()) {
return; // 数组为空，直接返回
}
minVal = nums[0]; // 初始化最小值为第一个元素
maxVal = nums[0]; // 初始化最大值为第一个元素
for (int num : nums) {
minVal = min(minVal, num); // 更新最小值
maxVal = max(maxVal, num); // 更新最大值
}
}
int main() {
vector<int> nums = {3, 7, 1, 9, 4, 5, 8, 2};
int minVal, maxVal;
findMinMax(nums, minVal, maxVal);
cout << "Min Value: " << minVal << endl;
cout << "Max Value: " << maxVal << endl;
return 0;
}
方法二：分治法
另一种更高效的方法是使用分治法。将数组分为两半，分别在左半部分和右半部分找到最大值和最小值，然后比较左右两部分的结果。
#include <iostream>
#include <vector>
using namespace std;
void findMinMaxRecursive(vector<int>& nums, int left, int right, int& minVal, int& maxVal) {
if (left == right) {
minVal = nums[left];
maxVal = nums[left];
return;
}
int mid = left + (right - left) / 2;
int leftMin, leftMax, rightMin, rightMax;
findMinMaxRecursive(nums, left, mid, leftMin, leftMax);
findMinMaxRecursive(nums, mid + 1, right, rightMin, rightMax);
minVal = min(leftMin, rightMin);
maxVal = max(leftMax, rightMax);
}
void findMinMax(vector<int>& nums, int& minVal, int& maxVal) {
if (nums.empty()) {
return; // 数组为空，直接返回
}
findMinMaxRecursive(nums, 0, nums.size() - 1, minVal, maxVal);
}
int main() {
vector<int> nums = {3, 7, 1, 9, 4, 5, 8, 2};
int minVal, maxVal;
findMinMax(nums, minVal, maxVal);
cout << "Min Value: " << minVal << endl;
cout << "Max Value: " << maxVal << endl;
return 0;
}
总结
本文介绍了两种寻找数组中最大值和最小值的算法：遍历数组和分治法。遍历数组是最简单的方法，但在数组较大时效率较低。分治法通过将数组分成多个子问题来提高效率。无论使用哪种方法，都可以在数组中轻松找到最大值和最小值。
