检查是否可以通过修改至少一个元素来使数组严格增加

本文概述

C ++
Java
C#
Python 3

给定一个正整数数组arr[]，任务是找出是否可以通过最多修改一个元素来严格增加这个数组。
例子：

输入：arr[] = {2, 4, 8, 6, 9, 12}
输出：YES
通过将8修改为5, 数组将严格增加。即{2, 4, 5, 6, 9, 12}
输入：arr[] = {10, 5, 2}
输出：NO

方法:对于每个arr[i]，如果它大于arr[i - 1]和arr[i + 1]，或者小于arr[i - 1]和arr[i + 1]，那么arr[i]需要修改。
即arr[i] = (arr[i - 1] + arr[i + 1]) / 2。如果修改后，arr[i] = arr[i - 1]或arr[i] = arr[i + 1]，则数组不能严格地增加而不影响超过一个元素。Else计数所有这些修改，如果最后的修改计数小于或等于1，则打印“Yes”否则打印“No”。
下面是上述方法的实现：
C ++

//C++ implementation of the approach #include < iostream> using namespace std; //Function that returns true if arr[] //can be made strictly increasing after //modifying at most one element bool check( int arr[], int n) { //To store the number of modifications //required to make the array //strictly increasing int modify = 0; //Check whether the first element needs //to be modify or not if (arr[0]> arr[1]) { arr[0] = arr[1] /2; modify++; }//Loop from 2nd element to the 2nd last element for ( int i = 1; i < n - 1; i++) {//Check whether arr[i] needs to be modified if ((arr[i - 1] < arr[i] & & arr[i + 1] < arr[i]) || (arr[i - 1]> arr[i] & & arr[i + 1]> arr[i])) {//Modifying arr[i] arr[i] = (arr[i - 1] + arr[i + 1]) /2; //Check if arr[i] is equal to any of //arr[i-1] or arr[i+1] if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1]) return false ; modify++; } }//Check whether the last element needs //to be modify or not if (arr[n - 1] < arr[n - 2]) modify++; //If more than 1 modification is required if (modify> 1) return false ; return true ; }//Driver code int main() { int arr[] = { 2, 4, 8, 6, 9, 12 }; int n = sizeof (arr) /sizeof (arr[0]); if (check(arr, n)) cout < < "Yes" < < endl; else cout < < "No" < < endl; return 0; }

Java

//Java implementation of the approach class GFG {//Function that returns true if arr[] //can be made strictly increasing after //modifying at most one element static boolean check( int arr[], int n) { //To store the number of modifications //required to make the array //strictly increasing int modify = 0 ; //Check whether the first element needs //to be modify or not if (arr[ 0 ]> arr[ 1 ]) { arr[ 0 ] = arr[ 1 ] /2 ; modify++; }//Loop from 2nd element to the 2nd last element for ( int i = 1 ; i < n - 1 ; i++) {//Check whether arr[i] needs to be modified if ((arr[i - 1 ] < arr[i] & & arr[i + 1 ] < arr[i]) || (arr[i - 1 ]> arr[i] & & arr[i + 1 ]> arr[i])) {//Modifying arr[i] arr[i] = (arr[i - 1 ] + arr[i + 1 ]) /2 ; //Check if arr[i] is equal to any of //arr[i-1] or arr[i+1] if (arr[i] == arr[i - 1 ] || arr[i] == arr[i + 1 ]) return false ; modify++; } }//Check whether the last element needs //to be modify or not if (arr[n - 1 ] < arr[n - 2 ]) modify++; //If more than 1 modification is required if (modify> 1 ) return false ; return true ; }//Driver code public static void main(String[] args) {int [] arr = { 2 , 4 , 8 , 6 , 9 , 12 }; int n = arr.length; if (check(arr, n)) System.out.print( "Yes" ); else System.out.print( "No" ); } }

//C# implementation of the approach using System; class GFG { //Function that returns true if arr[] //can be made strictly increasing after //modifying at most one element static bool check( int []arr, int n) { //To store the number of modifications //required to make the array //strictly increasing int modify = 0; //Check whether the first element needs //to be modify or not if (arr[0]> arr[1]) { arr[0] = arr[1] /2; modify++; } //Loop from 2nd element to the 2nd last element for ( int i = 1; i < n - 1; i++) { //Check whether arr[i] needs to be modified if ((arr[i - 1] < arr[i] & & arr[i + 1] < arr[i]) || (arr[i - 1]> arr[i] & & arr[i + 1]> arr[i])) { //Modifying arr[i] arr[i] = (arr[i - 1] + arr[i + 1]) /2; //Check if arr[i] is equal to any of //arr[i-1] or arr[i+1] if (arr[i] == arr[i - 1] || arr[i] == arr[i + 1]) return false ; modify++; } } //Check whether the last element needs //to be modify or not if (arr[n - 1] < arr[n - 2]) modify++; //If more than 1 modification is required if (modify> 1) return false ; return true ; } //Driver code public static void Main() { int [] arr = { 2, 4, 8, 6, 9, 12 }; int n = arr.Length; if (check(arr, n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } //This code is contributed by AnkitRai01

Python 3

# Python 3 implementation of above approach# Function that returns true if arr[] # can be made strictly increasing after # modifying at most one element def check( arr, n):# To store the number of modifications # required to make the array # strictly increasing modify = 0# Check whether the first element needs # to be modify or not if (arr[ 0 ]> arr[ 1 ]) : arr[ 0 ] = arr[ 1 ] //2 modify + = 1# Loop from 2nd element to the 2nd last element for i in range ( 1 , n - 1 ):# Check whether arr[i] needs to be modified if ((arr[i - 1 ] < arr[i] and arr[i + 1 ] < arr[i]) or (arr[i - 1 ]> arr[i] and arr[i + 1 ]> arr[i])):# Modifying arr[i] arr[i] = (arr[i - 1 ] + arr[i + 1 ]) //2# Check if arr[i] is equal to any of # arr[i-1] or arr[i+1] if (arr[i] = = arr[i - 1 ] or arr[i] = = arr[i + 1 ]): return Falsemodify + = 1# Check whether the last element needs # to be modify or not if (arr[n - 1 ] < arr[n - 2 ]): modify + = 1# If more than 1 modification is required if (modify> 1 ): return Falsereturn True# Driver code if __name__ = = "__main__" : arr = [ 2 , 4 , 8 , 6 , 9 , 12 ] n = len (arr)if (check(arr, n)): print ( "Yes" ) else : print ( "No" )# This code is contributed by ChitraNayal

【检查是否可以通过修改至少一个元素来使数组严格增加】输出如下：