Gegeben eine Reihe von N Elemente und eine Ganzzahl k . Die Aufgabe besteht darin, die Anzahl des Subarrays zu ermitteln, dessen maximales Element größer als K ist.
Beispiele:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice Anzahl der Subarrays Probieren Sie es aus!
Output : 3
All the possible subarrays of arr[] are
{ 1 } { 2 } { 3 } { 1 2 } { 2 3 }
{ 1 2 3 }.
Their maximum elements are 1 2 3 2 3 3.
There are only 3 maximum elements > 2.
Ansatz 1: Subarrays mit maximalem Element zählen<= K and then subtracting from total subarrays.
Die Idee besteht darin, das Problem dadurch anzugehen, dass Subarrays gezählt werden, deren maximales Element kleiner oder gleich k ist, da das Zählen solcher Subarrays einfacher ist. Um die Anzahl der Subarrays zu ermitteln, deren maximales Element kleiner oder gleich k ist, entfernen Sie alle Elemente, die größer als K sind, und ermitteln Sie die Anzahl der Subarrays mit den linken Elementen.
Sobald wir die obige Zahl gefunden haben, können wir sie von n*(n+1)/2 subtrahieren, um unser gewünschtes Ergebnis zu erhalten. Beachten Sie, dass es n*(n+1)/2 mögliche Anzahlen von Unterarrays eines beliebigen Arrays der Größe n geben kann. Wenn wir also die Anzahl der Subarrays ermitteln, deren maximales Element kleiner oder gleich K ist, und diese von n*(n+1)/2 subtrahieren, erhalten wir die Antwort.
Nachfolgend finden Sie die Umsetzung dieses Ansatzes:
C++// C++ program to count number of subarrays // whose maximum element is greater than K. #include
// Java program to count number of subarrays // whose maximum element is greater than K. import java.util.*; class GFG { // Return number of subarrays whose maximum // element is less than or equal to K. static int countSubarray(int arr[] int n int k) { // To store count of subarrays with all // elements less than or equal to k. int s = 0; // Traversing the array. int i = 0; while (i < n) { // If element is greater than k ignore. if (arr[i] > k) { i++; continue; } // Counting the subarray length whose // each element is less than equal to k. int count = 0; while (i < n && arr[i] <= k) { i++; count++; } // Summing number of subarray whose // maximum element is less than equal to k. s += ((count * (count + 1)) / 2); } return (n * (n + 1) / 2 - s); } // Driver code public static void main(String[] args) { int arr[] = { 1 2 3 }; int k = 2; int n = arr.length; System.out.print(countSubarray(arr n k)); } } // This code is contributed by Anant Agarwal.
# Python program to count # number of subarrays # whose maximum element # is greater than K. # Return number of # subarrays whose maximum # element is less than or equal to K. def countSubarray(arr n k): # To store count of # subarrays with all # elements less than # or equal to k. s = 0 # Traversing the array. i = 0 while (i < n): # If element is greater # than k ignore. if (arr[i] > k): i = i + 1 continue # Counting the subarray # length whose # each element is less # than equal to k. count = 0 while (i < n and arr[i] <= k): i = i + 1 count = count + 1 # Summing number of subarray whose # maximum element is less # than equal to k. s = s + ((count*(count + 1))//2) return (n*(n + 1)//2 - s) # Driver code arr = [1 2 3] k = 2 n = len(arr) print(countSubarray(arr n k)) # This code is contributed # by Anant Agarwal.
// C# program to count number of subarrays // whose maximum element is greater than K. using System; class GFG { // Return number of subarrays whose maximum // element is less than or equal to K. static int countSubarray(int[] arr int n int k) { // To store count of subarrays with all // elements less than or equal to k. int s = 0; // Traversing the array. int i = 0; while (i < n) { // If element is greater than k ignore. if (arr[i] > k) { i++; continue; } // Counting the subarray length whose // each element is less than equal to k. int count = 0; while (i < n && arr[i] <= k) { i++; count++; } // Summing number of subarray whose // maximum element is less than equal to k. s += ((count * (count + 1)) / 2); } return (n * (n + 1) / 2 - s); } // Driver code public static void Main() { int[] arr = {1 2 3}; int k = 2; int n = arr.Length; Console.WriteLine(countSubarray(arr n k)); } } // This code is contributed by vt_m.
<script> // Javascript program to count number of subarrays // whose maximum element is greater than K. // Return number of subarrays whose maximum // element is less than or equal to K. function countSubarray(arr n k) { // To store count of subarrays with all // elements less than or equal to k. let s = 0; // Traversing the array. let i = 0; while (i < n) { // If element is greater than k ignore. if (arr[i] > k) { i++; continue; } // Counting the subarray length whose // each element is less than equal to k. let count = 0; while (i < n && arr[i] <= k) { i++; count++; } // Summing number of subarray whose // maximum element is less than equal to k. s += parseInt((count * (count + 1)) / 2 10); } return (n * parseInt((n + 1) / 2 10) - s); } let arr = [1 2 3]; let k = 2; let n = arr.length; document.write(countSubarray(arr n k)); </script>
// PHP program to count number of subarrays // whose maximum element is greater than K. // Return number of subarrays whose maximum // element is less than or equal to K. function countSubarray( $arr $n $k) { // To store count of subarrays with all // elements less than or equal to k. $s = 0; // Traversing the array. $i = 0; while ($i < $n) { // If element is greater than k // ignore. if ($arr[$i] > $k) { $i++; continue; } // Counting the subarray length // whose each element is less // than equal to k. $count = 0; while ($i < $n and $arr[$i] <= $k) { $i++; $count++; } // Summing number of subarray whose // maximum element is less than // equal to k. $s += (($count * ($count + 1)) / 2); } return ($n * ($n + 1) / 2 - $s); } // Driven Program $arr = array( 1 2 3 ); $k = 2; $n = count($arr); echo countSubarray($arr $n $k); // This code is contributed by anuj_67. ?> Ausgabe
3
Zeitkomplexität: O(n).
Hilfsraum: O(1)
Ansatz 2: Zählen von Subarrays mit maximalem Element > K
Bei diesem Ansatz ermitteln wir einfach die Anzahl der Subarrays, die durch Einschließen eines Elements am Index i gebildet werden können, das größer als K ist. Nehmen wir also an arr [ i ] > K dann haben alle Subarrays, in denen dieses Element vorhanden ist, einen Wert, der größer als k ist, also berechnen wir einfach alle diese Subarrays für jedes Element, das größer als K ist, und addieren sie als Antwort. Wir initialisieren zunächst zwei Variablen Jahre = 0 Dies enthält Antwort und prev = -1 Dadurch wird der Index des vorherigen Elements verfolgt, das größer als K war.
Dazu benötigen wir lediglich drei Werte für jedes arr [ i ] > K .
- Anzahl der Subarrays beginnend mit dem Index ich . Das wird sein (N – i) . HINWEIS: Darin haben wir das Subarray eingefügt, das ein einzelnes Element enthält, das dieses Element selbst darstellt. { arr [ i ] }
- Anzahl der Subarrays, die an diesem Index enden ich Der Startindex dieser Subarrays liegt jedoch nach dem Index vorh des vorherigen Elements, das größer als K war, warum machen wir das? Denn für diese Elemente müssen wir unsere Antwort bereits berechnet haben, sodass wir dieselben Unterarrays nicht mehr als einmal zählen möchten. Dieser Wert wird also zustande kommen ( i - prev - 1 ) . HINWEIS: Hier subtrahieren wir 1, da wir bereits ein Subarray { arr [ i ] } gezählt haben, das sich selbst als einzelnes Element hat. Siehe obigen Punkthinweis.
- Anzahl der Subarrays mit einem Startindex kleiner als ich aber größer als vorh und Endindex größer als ich . Daher alle Subarrays, in denen arr[i] dazwischen liegt. Dies können wir berechnen, indem wir die beiden oben genannten Werte multiplizieren. Sagen wir sie als L = ( N - i - 1 ) Und R = ( i - prev -1 ). Jetzt multiplizieren wir einfach diese L und R, weil es für jeden Index auf der linken Seite von i einen R-Index gibt, der verschiedene Unterarrays zu einer grundlegenden mathematischen Sache machen kann. Das wird also L * R . Beachten Sie, dass wir hier im Wert von L tatsächlich 1 subtrahiert haben. Wenn wir dies nicht tun, schließen wir den Index i in unser L*R ein, was bedeutet, dass wir wieder Subarrays vom Typ Nummer 1 eingefügt haben. Siehe Punkt 1.
Nachfolgend finden Sie die Umsetzung dieses Ansatzes:
C++// C++ program to count number of subarrays // whose maximum element is greater than K. #include
// Java program to count number of subarrays // whose maximum element is greater than K. import java.util.*; public class GFG { static long countSubarray(int arr[] int n int k) { long ans = 0 ; int prev = - 1; //prev for keeping track of index of previous element > k; for(int i = 0 ; i < n ; i++ ) { if ( arr [ i ] > k ) { ans += n - i ; //subarrays starting at index i. ans += i - prev - 1 ; //subarrays ending at index i but starting after prev. ans += ( n - i - 1 ) * 1L * ( i - prev - 1 ) ; //subarrays having index i element in between. prev = i; // updating prev } } return ans; } // Driver code public static void main(String[] args) { int arr[] = { 4 5 1 2 3 }; int k = 2; int n = arr.length; System.out.print(countSubarray(arr n k)); } } //This Code is contributed by Manjeet Singh
# Python program to count number of subarrays # whose maximum element is greater than K. def countSubarray( arr n k): ans = 0 ; prev = - 1; #prev for keeping track of index of previous element > k; for i in range(0n): if ( arr [ i ] > k ) : ans += n - i ; #subarrays starting at index i. ans += i - prev - 1 ; #subarrays ending at index i but starting after prev. ans += ( n - i - 1 ) * ( i - prev - 1 ) ; #subarrays having index i element in between. prev = i; # updating prev return ans; # Driven Program arr = [ 4 5 1 2 3 ]; k = 2; n = len(arr); print(countSubarray(arr n k)); # this code is contributed by poojaagarwal2.
// C# program to count number of subarrays // whose maximum element is greater than K. using System; public class GFG { static long countSubarray(int[] arr int n int k) { long ans = 0; int prev = -1; // prev for keeping track of index of // previous element > k; for (int i = 0; i < n; i++) { if (arr[i] > k) { ans += n - i; // subarrays starting at index // i. ans += i - prev - 1; // subarrays ending at index i // but starting after prev. ans += (n - i - 1) * (long)1 * (i - prev - 1); // subarrays having index i // element in between. prev = i; // updating prev } } return ans; } // Driver code public static void Main(string[] args) { int[] arr = { 4 5 1 2 3 }; int k = 2; int n = arr.Length; Console.Write(countSubarray(arr n k)); } } // This Code is contributed by Karandeep1234
// Javascript program to count number of subarrays // whose maximum element is greater than K. function countSubarray(arr n k) { let ans = 0 ; //prev for keeping track of index of previous element > k; let prev = - 1; for(let i = 0 ; i < n ; i++ ) { if ( arr [ i ] > k ) { //subarrays starting at index i. ans += n - i ; //subarrays ending at index i but starting after prev. ans += i - prev - 1 ; //subarrays having index i element in between. ans += ( n - i - 1 ) * 1 * ( i - prev - 1 ) ; // updating prev prev = i; } } return ans; } // Driven Program let arr = [ 4 5 1 2 3 ]; let k = 2; let n = arr.length; document.write(countSubarray(arr n k));
Ausgabe
12
Zeitkomplexität: O(n).
Ansatz 3: Schiebefenstertechnik.
Algorithmus:
1. Initialisieren Sie eine Variable Jahre = 0 eine Variable maxElement = 0 und eine Variable Anzahl = 0 .
2. Durchlaufen Sie das Array und gehen Sie dabei für jedes Element wie folgt vor:
A. Wenn das aktuelle Element, d.h. arr[ i ] ist größer als das aktuelle Maximum. Aktualisieren Sie das Maximum, d. h. Das Radio = arr ] und den Zähler auf 0 zurücksetzen.
B. Wenn das aktuelle Element kleiner oder gleich dem aktuellen Maximum ist, erhöhen Sie die Anzahl.
C. Wenn maxElement ist dann größer als k Anzahl hinzufügen von Subarrays zur endgültigen Antwort und Aktualisierung der maxElement zum aktuellen Element.
3. Zurück Endgültige Antwort.
Hier ist die Implementierung der Schiebefenstertechnik.
C++#include
#include
import java.util.*; public class GFG { // Function to count the number of subarrays with the maximum element greater than k public static int countSubarray(int[] arr int n int k) { int maxElement = 0; // Variable to store the maximum element encountered so far int count = 0; // Variable to count the length of the subarray with elements <= k int ans = 0; // Variable to store the final result for (int i = 0; i < n; i++) { if (arr[i] > maxElement) { // If the current element is greater than the maximum element // update the maximum element and reset the count to zero. maxElement = arr[i]; count = 0; } else { // increment the count count++; } if (maxElement > k) { // If the maximum element in the current subarray is greater than k // add the count of subarrays ending at the current index (i - count + 1) to the result. ans += (i - count + 1); // Reset the maximum element and count to zero. maxElement = arr[i]; count = 0; } } // Return the final result return ans; } public static void main(String[] args) { int[] arr = {1 2 3 4}; int k = 1; int n = arr.length; // Call the countSubarray function to count the number of subarrays with maximum element greater than k int result = countSubarray(arr n k); System.out.println(result); } } // THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL
def countSubarray(arr n k): maxElement count ans = 0 0 0 for i in range(n): if arr[i] > maxElement: maxElement = arr[i] count = 0 else: count += 1 if maxElement > k: ans += (i - count + 1) maxElement = arr[i] count = 0 ans += (count * (count + 1)) // 2 return ans arr = [1 2 3 4] k = 1 n = len(arr) print(countSubarray(arr n k)) # This code is contributed by Vaibhav Saroj
using System; public class Program { public static int CountSubarray(int[] arr int n int k) { int maxElement = 0 count = 0 ans = 0; for(int i=0; i<n; i++) { if(arr[i] > maxElement) { maxElement = arr[i]; count = 0; } else { count++; } if(maxElement > k) { ans += (i - count + 1); maxElement = arr[i]; count = 0; } } ans += (count * (count + 1)) / 2; return ans; } public static void Main() { int[] arr = {1 2 3 4}; int k = 1; int n = arr.Length; Console.WriteLine(CountSubarray(arr n k)); } } // This code is contributed by Vaibhav Saroj
function countSubarray(arr n k) { let maxElement = 0 count = 0 ans = 0; for(let i=0; i<n; i++) { if(arr[i] > maxElement) { maxElement = arr[i]; count = 0; } else { count++; } if(maxElement > k) { ans += (i - count + 1); maxElement = arr[i]; count = 0; } } ans += (count * (count + 1)) / 2; return ans; } let arr = [1 2 3 4]; let k = 1; let n = arr.length; console.log(countSubarray(arr n k)); // This code is contributed by Vaibhav Saroj
Ausgabe
9
Die Sliding-Window-Technik wird beigesteuert von Vaibhav Saroj .
Zeitkomplexität: O( n ).
Raumkomplexität: O( 1 ).