Annettu joukko n elementtejä ja kokonaislukua k . Tehtävänä on löytää sen alitaulukon lukumäärä, jonka enimmäisalkio on suurempi kuin K.
Esimerkkejä:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice Subarray-luku Kokeile sitä!
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.
Lähestymistapa 1: Aliryhmien, joissa on max elementti, laskeminen<= K and then subtracting from total subarrays.
Ajatuksena on lähestyä ongelmaa laskemalla aliryhmiä, joiden maksimialkio on pienempi tai yhtä suuri kuin k, koska tällaisten aliryhmien laskeminen on helpompaa. Selvittääksesi niiden alitaulukoiden lukumäärän, joiden maksimialkio on pienempi tai yhtä suuri kuin k, poista kaikki alkio, joka on suurempi kuin K, ja etsi alitaulukon lukumäärä vasemmilla elementeillä.
Kun löydämme yllä olevan luvun, voimme vähentää sen arvosta n*(n+1)/2 saadaksemme vaaditun tuloksen. Huomaa, että minkä tahansa koon n taulukon alitaulukkoa voi olla n*(n+1)/2 mahdollista. Joten löytämällä sen alitaulukon lukumäärän, jonka maksimialkio on pienempi tai yhtä suuri kuin K ja vähentämällä se arvosta n*(n+1)/2, saamme vastauksen.
Alla on tämän lähestymistavan toteutus:
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. ?> Lähtö
3
Aika monimutkaisuus: O(n).
Aputila: O(1)
Lähestymistapa 2: Niiden aliryhmien laskeminen, joiden maksimielementti > K
Tässä lähestymistavassa löydämme yksinkertaisesti niiden aliryhmien lukumäärän, jotka voidaan muodostaa sisällyttämällä indeksiin i elementti, joka on suurempi kuin K. Jos siis oletetaan arr [i] > K silloin kaikilla aliryhmillä, joissa tämä elementti on, on arvo, joka on suurempi kuin k, joten laskemme kaikki nämä alitaulukot jokaiselle elementille, joka on suurempi kuin K, ja lisäämme ne vastaukseksi. Alustamme ensin kaksi muuttujaa vuotta = 0 tämä sisältää vastauksen ja edellinen = -1 tämä pitää kirjaa edellisen elementin indeksistä, joka oli suurempi kuin K.
Tätä varten tarvitsemme vain kolme arvoa jokaiselle arr [ i ] > K : lle .
- Aliryhmien lukumäärä indeksistä alkaen i . Tämä tulee olemaan ( N - i ) . HUOMAA: Olemme sisällyttäneet tähän alitaulukon, joka sisältää yhden elementin, joka on itse tämä elementti. { arr [ i ] }
- Tähän indeksiin päättyvien aliryhmien lukumäärä i mutta näiden aliryhmien aloitusindeksi on indeksin jälkeen Ed edellisestä elementistä, joka oli suurempi kuin K, miksi teemme tämän? Koska näille elementeille meidän täytyy olla jo laskeneet vastauksemme, jotta emme halua laskea samoja aliryhmiä useammin kuin kerran. Joten tämä arvo tulee olemaan ( i - edellinen - 1) . HUOMAA: Tässä vähennetään 1, koska olemme jo laskeneet alitaulukon { arr [ i ] }, jolla on itse yksi alkio. Katso yllä oleva huomautus.
- Niiden aliryhmien lukumäärä, joiden aloitusindeksi on pienempi kuin i mutta suurempi kuin Ed ja loppuindeksi suurempi kuin i . Siksi kaikki aliryhmät, joissa arr[i] on välissä. Tämä voidaan laskea kertomalla edellä mainitut kaksi arvoa. Sanotaan ne niin L = ( N - i - 1 ) ja R = (i - edellinen -1). Nyt vain kerrotaan nämä L ja R, koska jokaista 1:tä i:n vasemmalla puolella olevaa indeksiä kohden on R-indeksi, joka voi tehdä eri aliryhmistä matematiikan perusasia. Tästä siis tulee L*R. Huomaa tässä arvossa L, että olemme itse asiassa vähentäneet 1:n, jos emme tee tätä, sisällytämme indeksin i L*R:ään, mikä tarkoittaa, että olemme sisällyttäneet numero 1 -tyypin alijoukot uudelleen. Katso kohta 1.
Alla on tämän lähestymistavan toteutus:
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));
Lähtö
12
Aika monimutkaisuus: O(n).
Lähestymistapa 3: Liukuikkunatekniikka.
Algoritmi:
1. Alusta muuttuja vuotta = 0 muuttuja maxElement = 0 ja muuttuja laskenta = 0 .
2. Iteroi taulukon läpi seuraavasti kullekin elementille:
a. Jos nykyinen elementti eli arr[i] on suurempi kuin nykyinen maksimipäivitys maksimi ts. Radio = arr ] ja nollaa laskuri nollaan.
b. Jos nykyinen elementti on pienempi kuin nykyinen maksimi tai eual siihen, lisää määrää.
c. Jos maxElement on suurempi kuin k silloin lisää määrä aliryhmistä lopulliseen vastaukseen ja päivittämiseen maxElement nykyiseen elementtiin.
3. Palauta lopullinen vastaus.
Tässä on liukuikkunatekniikan toteutus.
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
Lähtö
9
Sliding Window Technique on mukana Vaibhav Saroj .
Aika monimutkaisuus: O(n).
Tilan monimutkaisuus: O( 1 ).