计算给定数组局部极值的C++代码
极值是指最小值或最大值。换句话说,它是一个数字或元素,它大于或小于其两个相邻值。
假设我们有一个包含n个元素的数组A。该数组A[i]中的一个元素被称为局部最小值,当且仅当它严格小于其两个相邻元素。如果它严格大于其相邻元素,则它将是局部最大值。对于A[0]和A[n-1],由于只有一个邻居,它们既不是最大值也不是最小值。我们必须找到给定数组中局部极值的个数。
对于给定的一组数字,第一个和最后一个数字永远不可能是极值。在给定的数组中,我们可以使用各种C++技术找到这样的局部极值。
输入输出场景
考虑数组中的一组N个元素。然后,我们可以计算数组中存在的局部极值的总数。
Input: numbers = 12, 16, 4 Output: 1 Input: numbers = 10, 16, 12, 5, 23, 40 Output: 2
使用for循环
在这种方法中,我们将使用一个for循环,该循环将从给定数组的第二个元素迭代到倒数第二个元素。这是因为第一个和最后一个元素永远不可能是极值。在循环中,我们将使用if语句检查每个元素是否大于或小于其两个相邻元素。如果任一条件为真,则num变量递增一。
示例
#include <iostream> using namespace std; int numberOfExtrema(int x[], int N){ int num = 0; // Iterate the loop from the second // element to the second last element for(int i = 1; i < N-1; i++){ if(x[i] > x[i-1] && x[i] > x[i+1]){ num++; } if(x[i] < x[i-1] && x[i] < x[i+1]){ num++; } } return num; } int main() { int x[] = {10, 16, 12, 5, 23, 40}; int N = sizeof(x) / sizeof(x[0]); std::cout << "Number of local extrema in the array: " << numberOfExtrema(x, N); return 0; }
输出
Number of local extrema in the array: 2
使用C++标准模板库
我们可以使用STL(标准模板库)算法的最大值和最小值运算。std::max()和std::min()是预定义函数,分别用于返回数组指定范围内的最大和最小元素。
语法
std::max_element(first, last) std::min_element(first, last)
其中,
first是范围开始元素的位置。
last是范围结束元素的位置。
如果我们想找到局部极值,我们需要一次考虑三个元素(当前元素及其两个相邻元素)。因此,我们的范围包含三个元素。因此,我们在大括号内指定这三个元素。
std::max({element 1, element 2, element 3});
这里,我们从给定数组的第二个元素迭代到倒数第二个元素。我们找到x[i - 1]、x[i]、x[i + 1]中的最大和最小元素。如果当前元素等于两者中的任何一个,则num递增一。
示例
让我们来看一个例子:
#include <iostream> #include <algorithm> using namespace std; int numberOfExtrema(int x[], int N){ int num = 0; // Iterate the loop from the second // Element to the second last element for (int i = 1; i < N - 1; i++) { int max_element = std::max({x[i - 1], x[i], x[i + 1]}); int min_element = std::min({x[i - 1], x[i], x[i + 1]}); if (x[i] == max_element || x[i] == min_element) { num++; } } return num; } int main() { int x[] = {10, 16, 12, 5, 23, 40}; int N = sizeof(x) / sizeof(x[0]); std::cout << "Number of local extrema in the array: " << numberOfExtrema(x,N); return 0; }
输出
Number of local extrema in the array: 2
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
使用递归
在这里,我们将使用递归来解决我们的问题。我们将数组划分为更小的子数组,并在其中找到中心值。然后,我们检查中心元素是否大于或小于其两个相邻元素。
如果满足任一条件,则num变量递增一。由于递归函数自身调用,所有结果都将组合以给出最终输出。
示例
#include <iostream> int recursion(int x[], int left, int right) { // If subarray contains 2 or less elements if (right - left <= 1) { return 0; } int center = left + (right - left) / 2; int num = 0; if ((x[center] > x[center - 1] && x[center] > x[center + 1]) || (x[center] < x[center - 1] && x[center] < x[center + 1])) { num++; } num += recursion(x, left, center); num += recursion(x, center, right); return num; } int numberOfExtrema(int x[], int N) { return recursion(x, 0, N - 1); } int main() { int x[] = {10, 16, 12, 5, 23, 40}; int N = sizeof(x) / sizeof(x[0]); std::cout << "Number of local extrema in the array: " << numberOfExtrema(x, N) << std::endl; return 0; }
输出
Number of local extrema in the array: 2
结论
在本文中,我们讨论了在数组中查找局部极值的几种不同方法。在第一种方法中,我们学习了简单的迭代方法,其中涉及使用for循环。在第二种方法中,我们使用了std::max()和std::min()函数。在第三种方法中,我们讨论了递归方法,该方法对于较大的数组很有用。