计算给定数组局部极值的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变量递增一。

示例

Open Compiler
#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递增一。

示例

让我们来看一个例子:

Open Compiler
#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变量递增一。由于递归函数自身调用,所有结果都将组合以给出最终输出。

示例

Open Compiler
#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()函数。在第三种方法中,我们讨论了递归方法,该方法对于较大的数组很有用。

更新于:2024年1月5日

667 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告