Gitt en rekke n elementer og et heltall k . Oppgaven er å finne antallet til underarrayen som har et maksimumselement større enn K.
Eksempler:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice Antall undermatriser Prøv det!
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.
Tilnærming 1: Telle undermatriser med maks element<= K and then subtracting from total subarrays.
Ideen er å nærme seg problemet ved å telle subarrays hvis maksimale element er mindre enn eller lik k, da det er lettere å telle slike subarrays. For å finne antallet undermatriser hvis maksimale element er mindre enn eller lik k, fjern alle elementene som er større enn K og finn antallet undermatriser med de venstre elementene.
Når vi finner tellingen ovenfor, kan vi trekke den fra n*(n+1)/2 for å få det nødvendige resultatet. Legg merke til at det kan være n*(n+1)/2 mulig antall undermatriser av en hvilken som helst matrise med størrelse n. Så ved å finne antallet undermatriser hvis maksimale element er mindre enn eller lik K og trekke det fra n*(n+1)/2 får vi svaret.
Nedenfor er implementeringen av denne tilnærmingen:
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. ?> Produksjon
3
Tidskompleksitet: O(n).
Hjelpeområde: O(1)
Tilnærming 2: Telle undermatriser med makselement > K
I denne tilnærmingen finner vi ganske enkelt antallet undermatriser som kan dannes ved å inkludere et element ved indeks i som er større enn K. Derfor hvis anta arr [i] > K da vil alle undermatrisene der dette elementet er tilstede ha en verdi som er større enn k, så vi beregner bare alle disse undergruppene for hvert element som er større enn K og legger dem til som svar. Vi initialiserer først to variabler år = 0 denne inneholder svar og forrige = -1 dette holder styr på indeksen til forrige element som var større enn K.
For å gjøre dette trenger vi bare tre verdier for hver arr [i] > K.
- Antall undermatriser som starter fra indeksen jeg . Dette vil være ( N - i ) . MERK: I dette har vi inkludert underarrayen som inneholder enkeltelementet som er selve elementet. { arr [i] }
- Antall undermatriser som slutter på denne indeksen jeg men startindeksen til disse undergruppene er etter indeksen forrige av forrige element som var større enn K, hvorfor gjør vi dette? Fordi for de elementene må vi allerede ha beregnet svaret vårt, så vi ønsker ikke å telle de samme undergruppene mer enn én gang. Så denne verdien kommer til å bli ( i - forrige - 1) . MERK: I dette trekker vi fra 1 fordi vi allerede har telt en undergruppe {arr [i] } som har seg selv som enkeltelement. Se punktnotat ovenfor.
- Antall undermatriser med startindeks mindre enn jeg men større enn forrige og sluttindeks større enn jeg . Derfor alle undermatriser der arr[i] er i mellom. Dette kan vi beregne ved å multiplisere over to verdier. La oss si dem som L = ( N - i - 1 ) og R = (i - forrige -1). Nå multipliserer vi bare disse L og R fordi for hver 1 indeks på venstre side av i er det R-indekser som kan gjøre forskjellige undergrupper til grunnleggende matematikk. Så dette blir L * R . Legg merke til her i val av L at vi faktisk har trukket 1 hvis vi ikke gjør dette, så inkluderer vi indeks i i vår L*R, noe som betyr at vi har inkludert nummer 1 type subarrays igjen. Se punkt 1.
Nedenfor er implementeringen av denne tilnærmingen:
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));
Produksjon
12
Tidskompleksitet: O(n).
Tilnærming 3: Skyvevindusteknikk.
Algoritme:
1. Initialiser en variabel år = 0 en variabel maxElement = 0 og en variabel telle = 0 .
2. Iterer gjennom matrisen og gjør følgende for hvert element:
en. Hvis det nåværende elementet dvs. arr[ i ] er større enn gjeldende maksimum oppdatering den maksimale dvs. Radioen = arr ] og tilbakestill telleren til 0.
b. Hvis det gjeldende elementet er mindre enn eller eual til gjeldende maksimum, øker du antallet.
c. Hvis maxElement er grteater enn k da legg til antall av undergrupper til endelig svar og oppdater maxElement til gjeldende element.
3. Tilbake Endelig svar.
Her er implementeringen av skyvevinduteknikken.
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
Produksjon
9
Skyvevindusteknikken er bidratt av Vaibhav Saroj .
Tidskompleksitet: O( n ).
Romkompleksitet: O( 1 ).