logo

TechCodeview

Déterminer si un sous-réseau a la forme d'une montagne ou non

Essayez-le sur GfG Practice ' title= #practiceLinkDiv { display : aucun !important; }

On nous donne un tableau d'entiers et une plage dont nous avons besoin pour déterminer si le sous-tableau qui se situe dans cette plage a des valeurs en forme de montagne ou non. Toutes les valeurs du sous-tableau sont dites avoir la forme d'une montagne si toutes les valeurs augmentent ou diminuent ou augmentent d'abord puis diminuent. 
Plus formellement un sous-tableau [a1 a2 a3…an] est dit en forme de montagne s'il existe un entier K 1<= K <= N such that 
a1<= a2 <= a3 .. <= aK >= une(K+1) >= une(K+2) …. >= unN  

Exemples :  

  Input : Arr[]   = [2 3 2 4 4 6 3 2] Range = [0 2]   Output :    Yes   Explanation:   The output is yes  subarray is [2 3 2] so subarray first increases and then decreases   Input:    Arr[] = [2 3 2 4 4 6 3 2] Range = [2 7]   Output:   Yes   Explanation:   The output is yes  subarray is [2 4 4 6 3 2] so subarray first increases and then decreases   Input:   Arr[]= [2 3 2 4 4 6 3 2] Range = [1 3]   Output:   no   Explanation:   The output is no subarray is [3 2 4] so subarray is not in the form above stated
Recommended Practice Problème de sous-réseau de montagne Essayez-le !

Solution:  



    Approche:Le problème comporte plusieurs requêtes, donc pour chaque requête, la solution doit être calculée avec le moins de complexité temporelle possible. Créez donc deux espaces supplémentaires de la longueur du tableau d'origine. Pour chaque élément, trouver le dernier index du côté gauche qui augmente, c'est-à-dire supérieur à son élément précédent et trouver l'élément du côté droit stockera le premier index du côté droit qui diminue, c'est-à-dire supérieur à son élément suivant. Si ces valeurs peuvent être calculées pour chaque indice en temps constant, alors pour chaque plage donnée, la réponse peut être donnée en temps constant.Algorithme: 
    1. Créez deux espaces de longueur supplémentaires n gauche et droite et une variable supplémentaire dernier point
    2. Initialiser gauche[0] = 0 et dernier point = 0
    3. Parcourez le tableau d'origine du deuxième index à la fin
    4. Pour chaque index, vérifiez s'il est supérieur à l'élément précédent. Si oui, mettez à jour le dernier point avec l'indice actuel.
    5. Pour chaque magasin d'index, le dernier point dans gauche[i]
    6. initialiser à droite[N-1] = N-1 et dernier point = N-1
    7. Parcourez le tableau d'origine de l'avant-dernier index au début
    8. Pour chaque index, vérifiez s'il est supérieur à l'élément suivant. Si oui, mettez à jour le dernier point avec l'indice actuel.
    9. Pour chaque magasin d'index, le dernier point dans c'est vrai[i]
    10. Traitez maintenant les requêtes
    11. pour chaque requête lr si droite[l] >= gauche[r] puis imprimez Oui autre Non
    Mise en œuvre:
C++ 
// C++ program to check whether a subarray is in // mountain form or not #include    using namespace std; // Utility method to construct left and right array int preprocess(int arr[] int N int left[] int right[]) {  // Initialize first left index as that index only  left[0] = 0;  int lastIncr = 0;  for (int i = 1; i < N; i++)  {  // if current value is greater than previous  // update last increasing  if (arr[i] > arr[i - 1])  lastIncr = i;  left[i] = lastIncr;  }  // Initialize last right index as that index only  right[N - 1] = N - 1;  int firstDecr = N - 1;  for (int i = N - 2; i >= 0; i--)  {  // if current value is greater than next  // update first decreasing  if (arr[i] > arr[i + 1])  firstDecr = i;  right[i] = firstDecr;  } } // Method returns true if arr[L..R] is in mountain form bool isSubarrayMountainForm(int arr[] int left[]  int right[] int L int R) {  // return true only if right at starting range is  // greater than left at ending range  return (right[L] >= left[R]); } // Driver code to test above methods int main() {  int arr[] = {2 3 2 4 4 6 3 2};  int N = sizeof(arr) / sizeof(int);  int left[N] right[N];  preprocess(arr N left right);  int L = 0;  int R = 2;  if (isSubarrayMountainForm(arr left right L R))  cout << 'Subarray is in mountain formn';  else  cout << 'Subarray is not in mountain formn';  L = 1;  R = 3;  if (isSubarrayMountainForm(arr left right L R))  cout << 'Subarray is in mountain formn';  else  cout << 'Subarray is not in mountain formn';  return 0; }
Java 
// Java program to check whether a subarray is in // mountain form or not class SubArray {  // Utility method to construct left and right array  static void preprocess(int arr[] int N int left[] int right[])  {  // initialize first left index as that index only  left[0] = 0;  int lastIncr = 0;    for (int i = 1; i < N; i++)  {  // if current value is greater than previous  // update last increasing  if (arr[i] > arr[i - 1])  lastIncr = i;  left[i] = lastIncr;  }    // initialize last right index as that index only  right[N - 1] = N - 1;  int firstDecr = N - 1;    for (int i = N - 2; i >= 0; i--)  {  // if current value is greater than next  // update first decreasing  if (arr[i] > arr[i + 1])  firstDecr = i;  right[i] = firstDecr;  }  }    // method returns true if arr[L..R] is in mountain form  static boolean isSubarrayMountainForm(int arr[] int left[]  int right[] int L int R)  {  // return true only if right at starting range is  // greater than left at ending range  return (right[L] >= left[R]);  }    public static void main(String[] args)  {  int arr[] = {2 3 2 4 4 6 3 2};  int N = arr.length;  int left[] = new int[N];  int right[] = new int[N];  preprocess(arr N left right);  int L = 0;  int R = 2;    if (isSubarrayMountainForm(arr left right L R))  System.out.println('Subarray is in mountain form');  else  System.out.println('Subarray is not in mountain form');    L = 1;  R = 3;    if (isSubarrayMountainForm(arr left right L R))  System.out.println('Subarray is in mountain form');  else  System.out.println('Subarray is not in mountain form');  } } // This Code is Contributed by Saket Kumar
Python3 
# Python 3 program to check whether a subarray is in # mountain form or not # Utility method to construct left and right array def preprocess(arr N left right): # initialize first left index as that index only left[0] = 0 lastIncr = 0 for i in range(1N): # if current value is greater than previous # update last increasing if (arr[i] > arr[i - 1]): lastIncr = i left[i] = lastIncr # initialize last right index as that index only right[N - 1] = N - 1 firstDecr = N - 1 i = N - 2 while(i >= 0): # if current value is greater than next # update first decreasing if (arr[i] > arr[i + 1]): firstDecr = i right[i] = firstDecr i -= 1 # method returns true if arr[L..R] is in mountain form def isSubarrayMountainForm(arr left right L R): # return true only if right at starting range is # greater than left at ending range return (right[L] >= left[R]) # Driver code  if __name__ == '__main__': arr = [2 3 2 4 4 6 3 2] N = len(arr) left = [0 for i in range(N)] right = [0 for i in range(N)] preprocess(arr N left right) L = 0 R = 2 if (isSubarrayMountainForm(arr left right L R)): print('Subarray is in mountain form') else: print('Subarray is not in mountain form') L = 1 R = 3 if (isSubarrayMountainForm(arr left right L R)): print('Subarray is in mountain form') else: print('Subarray is not in mountain form') # This code is contributed by # Surendra_Gangwar
C# 
// C# program to check whether  // a subarray is in mountain  // form or not using System; class GFG {    // Utility method to construct   // left and right array  static void preprocess(int []arr int N   int []left int []right)  {  // initialize first left   // index as that index only  left[0] = 0;  int lastIncr = 0;    for (int i = 1; i < N; i++)  {  // if current value is   // greater than previous  // update last increasing  if (arr[i] > arr[i - 1])  lastIncr = i;  left[i] = lastIncr;  }    // initialize last right   // index as that index only  right[N - 1] = N - 1;  int firstDecr = N - 1;    for (int i = N - 2; i >= 0; i--)  {  // if current value is   // greater than next  // update first decreasing  if (arr[i] > arr[i + 1])  firstDecr = i;  right[i] = firstDecr;  }  }    // method returns true if  // arr[L..R] is in mountain form  static bool isSubarrayMountainForm(int []arr int []left  int []right int L int R)  {  // return true only if right at   // starting range is greater   // than left at ending range  return (right[L] >= left[R]);  }      // Driver Code  static public void Main ()  {  int []arr = {2 3 2 4  4 6 3 2};  int N = arr.Length;  int []left = new int[N];  int []right = new int[N];  preprocess(arr N left right);    int L = 0;  int R = 2;    if (isSubarrayMountainForm(arr left   right L R))  Console.WriteLine('Subarray is in ' +   'mountain form');  else  Console.WriteLine('Subarray is not ' +   'in mountain form');    L = 1;  R = 3;    if (isSubarrayMountainForm(arr left   right L R))  Console.WriteLine('Subarray is in ' +   'mountain form');  else  Console.WriteLine('Subarray is not ' +   'in mountain form');  } } // This code is contributed by aj_36
JavaScript 
<script>  // Javascript program to check whether   // a subarray is in mountain   // form or not    // Utility method to construct   // left and right array  function preprocess(arr N left right)  {  // initialize first left   // index as that index only  left[0] = 0;  let lastIncr = 0;    for (let i = 1; i < N; i++)  {  // if current value is   // greater than previous  // update last increasing  if (arr[i] > arr[i - 1])  lastIncr = i;  left[i] = lastIncr;  }    // initialize last right   // index as that index only  right[N - 1] = N - 1;  let firstDecr = N - 1;    for (let i = N - 2; i >= 0; i--)  {  // if current value is   // greater than next  // update first decreasing  if (arr[i] > arr[i + 1])  firstDecr = i;  right[i] = firstDecr;  }  }    // method returns true if  // arr[L..R] is in mountain form  function isSubarrayMountainForm(arr left right L R)  {  // return true only if right at   // starting range is greater   // than left at ending range  return (right[L] >= left[R]);  }    let arr = [2 3 2 4 4 6 3 2];  let N = arr.length;  let left = new Array(N);  let right = new Array(N);  preprocess(arr N left right);  let L = 0;  let R = 2;  if (isSubarrayMountainForm(arr left right L R))  document.write('Subarray is in ' + 'mountain form' + '
');  else  document.write('Subarray is not ' + 'in mountain form' + '
');  L = 1;  R = 3;  if (isSubarrayMountainForm(arr left right L R))  document.write('Subarray is in ' + 'mountain form');  else  document.write('Subarray is not ' + 'in mountain form');   </script>
    Sortir: 
Subarray is in mountain form Subarray is not in mountain form
    Analyse de complexité : 
      Complexité temporelle :Sur). 
      Seules deux traversées sont nécessaires, la complexité temporelle est donc O(n).Complexité spatiale :Sur). 
      Deux espaces supplémentaires de longueur n sont nécessaires, la complexité spatiale est donc O(n).


 

chaîne de format Java
Créer un quiz