C++程序 计算本地极值个数
给定n个元素的数组。本地极值是指要么大于其两个邻居,要么小于其两个邻居的元素。您必须计算给定数组中的本地极值数量。
注意: 第一个和最后一个元素不是本地极值。
例子:
输入:a[] = {1, 5, 2, 5}
输出:2
输入:a[] = {1, 2, 3}
输出:0
方法: 计算极值的数量,我们必须检查一个元素是maxima或minima,即它是否比其邻居更大或者比邻居更小。为此,简单地遍历数组,并对每个元素检查其作为极值的可能性。
注意: a[0] 和 a[n-1] 每个只有一个邻居,他们既不是最小值也不是最大值。
// CPP to find number
// of extrema
#include <bits/stdc++.h>
using namespace std;
// function to find
// local extremum
int extrema(int a[], int n)
{
int count = 0;
// start loop from position 1
// till n-1
for (int i = 1; i < n - 1; i++)
{
// only one condition
// will be true at a
// time either a[i]
// will be greater than
// neighbours or less
// than neighbours
// check if a[i] is greater
// than both its neighbours
// then add 1 to x
count += (a[i] > a[i - 1] && a[i] > a[i + 1]);
// check if a[i] is
// less than both its
// neighbours, then
// add 1 to x
count += (a[i] < a[i - 1] && a[i] < a[i + 1]);
}
return count;
}
// driver program
int main()
{
int a[] = { 1, 0, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
cout << extrema(a, n);
return 0;
}
输出:
2
时间复杂度: 输入数组的大小为n,则为O(n)。这是因为for循环从1到n执行。