数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在最多一次替换后，最小化给定数组中峰值和谷值的个数
峰值定义为数组中左右两侧的值都小于该索引值的位置或索引。谷值定义为数组中左右两侧的值都大于该索引值的位置或索引。在这个问题中，我们给定一个大小为 n 的整数数组 'array'。我们的任务是通过执行一个操作来最小化或减少给定数组的峰值和谷值的个数。操作是指我们最多可以将给定数组的一个值替换为任何值。
注意：在上述问题的解释中，我们提到了峰值和谷值，因此请明确，给定数组的第 0 个索引和最后一个索引既不被认为是峰值也不被认为是谷值，因为它们没有两个相邻元素。
示例
输入
n: 5 array: [2, 1, 3, 2, 6]
输出
0
解释：在上述大小为 5 的数组中，通过将第二个索引值 3 替换为 1，峰值和谷值的个数变为 0。因此，新数组变为 [2, 1, 1, 2, 6]。
输入
n: 6 array: [2, 1, 3, 4, 3, 4]
输出
1
贪心算法
这种方法的思想很简单，我们贪心地思考，因为我们知道任何索引 i 都可能影响 i+1 或 i-1 索引，所以我们尝试更改受最大索引数影响的索引 i 的值。
让我们逐步讨论这种方法：
在这里，我们创建了三个函数 'minCountOfPeaksTrougs'、'next' 和 'previous'。
在 'minCountOfPeaksTrougs' 函数中
创建一个布尔数组，通过遍历数组来标记峰值和谷值数组，并计算它们的个数。
将峰值和谷值的个数存储在变量 result 中。
再次遍历数组，我们检查当前索引 i 的下一个和上一个索引，分别将当前数组值赋值为下一个数组值和上一个数组值，并使用 next 和 previous 函数更新它。
最后更新结果并返回它。
在 Next 和 previous 函数中
这两个函数都采用参数，例如当前索引、数组和数组的长度，并分别验证当前索引是否具有峰值和谷值。
让我们看下面的代码，以便更好地理解上述方法。
示例
#include <bits/stdc++.h>
using namespace std;
// Create a function to check the next element for the current index
bool next(int i, int array[], int n){
bool ok;
ok = i > 0 && i < n - 1 && array[i] < array[i - 1] && array[i] < array[i + 1];
return ok;
}
// Create a function to check the previous element for the current index
bool previous(int i, int array[], int n){
bool ok;
ok = i > 0 && i < n - 1 && array[i] > array[i - 1] && array[i] > array[i + 1];
return ok;
}
// Create function minCountOfPeaksTrougs to minimize the count of Peaks and Trough
int minCountOfPeaksTrougs(int array[], int n){
// Create an array of boolean to store the index of peaks and troughs
bool check[n] = { 0 };
int cnt = 0;
// Traverse given array to check the troughs and peaks
for (int i = 1; i < n- 1; i++) {
//If both the neighbors are greater than the current index is peaks
if (array[i] > array[i - 1] && array[i] > array[i + 1]){
check[i] = 1;
cnt++;
}
//If both the neighbors are smaller than the current index is trough
else if (array[i] < array[i - 1] && array[i] < array[i + 1]){
check[i] = 1;
cnt++;
}
}
// Create variable result and initialized With the count of peaks and troughs
int result = cnt;
// Traverse the array
for (int i = 1; i < n - 1; i++) {
int curVal = array[i];
// If we make the current array value as next array value
array[i] = array[i + 1];
int temp = cnt -check[i - 1] -check[i] -check[i + 1] +next(i - 1, array, n) +previous(i - 1, array, n) +next(i, array, n) +previous(i, array, n) +next(i + 1, array, n) +previous(i + 1, array, n);
result= min( result, temp );
// If we make current array value as the previous array value
array[i] = array[i - 1];
temp = cnt -check[i - 1] -check[i] -check[i + 1] +next(i - 1, array, n) +previous(i - 1, array, n) +next(i, array, n) +previous(i, array, n) +next(i + 1, array, n) +previous(i + 1, array, n);
result= min( result, temp );
array[i] = curVal;
}
return result;
}
int main(){
// Given Array
int array[] = { 2, 1, 3, 2, 6 };
// Getting the size of the given array
int n = sizeof(array) / sizeof(int);
// Store minimum count of peaks and troughs by calling the minCountOfPeaksTrougs function
int res = minCountOfPeaksTrougs(array, n);
cout << "Minimum Count of Peaks and Troughs are: "<< res;
return 0;
}
输出
Minimum Count of Peaks and Troughs are: 0
时间和空间复杂度
上述代码的时间复杂度为 O(N)，因为我们遍历了数组。
上述代码的空间复杂度为 O(N)，因为我们存储了峰值和谷值的个数。
其中 N 是数组的大小。
结论
在本教程中，我们实现了一个 C++ 程序，用于在最多一次替换后最小化给定数组中峰值和谷值的个数。我们实现了一种贪心算法。时间复杂度为 O(N)，空间复杂度为 O(N)。其中 N 是数组的大小。
48 次浏览
