logo

TechCodeview

Zoek of een subarray de vorm van een berg heeft of niet

Probeer het eens op GfG Practice ' title= #practiceLinkDiv {weergave: geen! belangrijk; }

We krijgen een array van gehele getallen en een bereik dat we moeten vinden om te bepalen of de subarray die binnen dit bereik valt waarden in de vorm van een berg heeft of niet. Er wordt gezegd dat alle waarden van de subarray de vorm van een berg hebben als alle waarden stijgen of dalen, of eerst stijgen en dan dalen. 
Meer formeel een subarray [a1 a2 a3…aN] er wordt gezegd dat het de vorm van een berg heeft als er een geheel getal K 1 bestaat<= K <= N such that 
een1<= a2 <= a3 .. <= aK >= een(K+1) >= een(K+2) …. >= eenN  

Voorbeelden:  

  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 Mountain Subarray-probleem Probeer het!

Oplossing:  



    Benadering:Het probleem heeft meerdere query's, dus voor elke query moet de oplossing worden berekend met zo min mogelijk tijdscomplexiteit. Creëer dus twee extra spaties met de lengte van de originele array. Zoek voor elk element de laatste index aan de linkerkant die toeneemt, d.w.z. groter dan het vorige element, en zoek het element aan de rechterkant om de eerste index aan de rechterkant op te slaan, die afneemt, d.w.z. groter dan het volgende element. Als deze waarden voor elke index in constante tijd kunnen worden berekend, kan voor elk gegeven bereik het antwoord in constante tijd worden gegeven.Algoritme: 
    1. Creëer twee extra lengteruimtes N links En rechts en een extra variabele laatsteptr
    2. Initialiseren links[0] = 0 en laatsteptr = 0
    3. Doorloop de originele array van de tweede index naar het einde
    4. Controleer voor elke index of deze groter is dan het vorige element, zo ja, update dan de laatsteptr met de huidige index.
    5. Voor elke index slaat u de laatsteptr in links[ik]
    6. initialiseren rechts[N-1] = N-1 en laatsteptr = N-1
    7. Doorloop de originele array vanaf de voorlaatste index tot aan het begin
    8. Controleer voor elke index of deze groter is dan het volgende element. Zo ja, update dan de laatsteptr met de huidige index.
    9. Voor elke index slaat u de laatsteptr in rechts[ik]
    10. Verwerk nu de vragen
    11. voor elke vraag l r als rechts[l] >= links[r] druk vervolgens af Ja anders Nee
    Uitvoering:
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>
    Uitgang: 
Subarray is in mountain form Subarray is not in mountain form
    Complexiteitsanalyse: 
      Tijdcomplexiteit:Op). 
      Er zijn slechts twee traversals nodig, dus de tijdscomplexiteit is O(n).Ruimtecomplexiteit:Op). 
      Er zijn twee extra ruimten met lengte n nodig, dus de ruimtecomplexiteit is O(n).


 

Quiz maken