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

本文概述

• 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#

//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 False
  
             modify + = 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 False
  
     return 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

输出如下：

Yes

---