Adott egy tömb n elemek és egy egész szám k . A feladat annak a résztömbnek a száma, amelynek a maximális eleme nagyobb, mint K.
Példák:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice Subrays grófja Próbáld ki!
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.
1. megközelítés: Maximum elemmel rendelkező alrendszerek számlálása<= K and then subtracting from total subarrays.
Az ötlet az, hogy a problémát úgy közelítsük meg, hogy megszámoljuk azokat az altömböket, amelyek maximális eleme kisebb vagy egyenlő, mint k, mivel az ilyen altömböket könnyebb megszámolni. Annak a résztömbnek a számának meghatározásához, amelynek maximális eleme kisebb vagy egyenlő, mint k, távolítson el minden olyan elemet, amely nagyobb, mint K, és keresse meg a bal oldali elemekkel rendelkező altömb számát.
Ha megtaláltuk a fenti számot, kivonhatjuk n*(n+1)/2-ből, hogy megkapjuk a kívánt eredményt. Figyeljük meg, hogy bármely n méretű tömbnek n*(n+1)/2 lehetséges számú altömbje lehet. Tehát, ha megtaláljuk annak a résztömbnek a számát, amelynek maximális eleme kisebb vagy egyenlő, mint K, és kivonjuk az n*(n+1)/2-ből, megkapjuk a választ.
Az alábbiakban bemutatjuk ennek a megközelítésnek a megvalósítását:
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. ?> Kimenet
3
Időbonyolultság: O(n).
Segédtér: O(1)
2. megközelítés: Olyan alrendszerek megszámlálása, amelyeknek max eleme > K
Ebben a megközelítésben egyszerűen megtaláljuk azoknak az altömböknek a számát, amelyeket úgy alakíthatunk ki, hogy az i indexben olyan elemet veszünk, amely nagyobb, mint K. Ezért ha tegyük fel arr [ i ] > K akkor az összes altömb, amelyben ez az elem jelen van, k-nál nagyobb értékű lesz, ezért csak kiszámítjuk az összes altömböt minden olyan elemhez, amely nagyobb K-nál, és válaszként hozzáadjuk őket. Először inicializálunk két változót év = 0 ez tartalmazza a választ és előző = -1 ez nyomon követi az előző elem indexét, amely nagyobb volt, mint K.
Ehhez mindössze három értékre van szükségünk minden arr [i]>K-hoz.
- Altömbök száma az indextől kezdve én . Ez lesz ( N - i ) . MEGJEGYZÉS: Ebbe belefoglaltuk az egyetlen elemet tartalmazó altömböt, amely maga ez az elem. { arr [ i ] }
- Az ezen az indexen végződő altömbök száma én de ezen altömbök kezdő indexe az index után van előz az előző elemből, amely nagyobb volt, mint K, miért tesszük ezt? Mert ezekre az elemekre már ki kell számítanunk a választ, hogy ne akarjuk többször megszámolni ugyanazokat az altömböket. Tehát ez az érték meg fog jelenni ( i - előző - 1 ) . MEGJEGYZÉS: Ebben az esetben kivonunk 1-et, mert már megszámoltunk egy { arr [ i ] } altömböt, amelynek önmagában egyetlen eleme van. Lásd a fenti pont megjegyzését.
- Azon altáblák száma, amelyek kezdő indexe kisebb, mint én de nagyobb mint előz és a végindex nagyobb, mint én . Ezért minden olyan altömb, amelyben arr[i] között van. Ezt úgy tudjuk kiszámítani, hogy a fenti két értéket megszorozzuk. Mondjuk őket úgy L = ( N - i - 1 ) és R = ( i - előző -1 ). Most csak megszorozzuk ezeket az L-t és az R-t, mert az i bal oldalán minden 1 indexhez van R index, amely a különböző altömböket alapvető matematikai dologgá teszi. Tehát ez lesz L*R. Vegyük észre, hogy L értékéből valójában kivontuk az 1-et, ha ezt nem tesszük meg, akkor az i indexet belevesszük az L*R-be, ami azt jelenti, hogy ismét belefoglaltuk az 1-es típusú altömböket. Lásd az 1. pontot.
Az alábbiakban bemutatjuk ennek a megközelítésnek a megvalósítását:
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));
Kimenet
12
Időbonyolultság: O(n).
3. megközelítés: Tolóablak technika.
Algoritmus:
1. Változó inicializálása év = 0 egy változó maxElement = 0 és egy változó szám = 0 .
2. Ismételje meg a tömböt, és tegye a következőket minden elemhez:
a. Ha az aktuális elem pl. arr[i] nagyobb, mint az aktuális maximum frissítés a maximum, azaz A rádió = arr ] és állítsa vissza a számlálót 0-ra.
b. Ha az aktuális elem kisebb vagy eual, mint az aktuális maximum, akkor növelje a számlálást.
c. Ha maxElement akkor grteaterebb, mint k szám hozzáadása részegységek közül a végső válaszhoz és a frissítéshez maxElement az aktuális elemhez.
3. Vissza a végső válasz.
Íme a csúszóablak technika megvalósítása.
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
Kimenet
9
A tolóablak technikához hozzájárul Vaibhav Saroj .
Időbonyolultság: O( n ).
Térkomplexitás: O( 1 ).