資料結構
網路
關係資料庫管理系統 (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 次瀏覽
