Biorąc pod uwagę tablicę N elementy i liczbę całkowitą k . Zadanie polega na znalezieniu liczby podtablicy, w której maksymalny element jest większy od K.
Przykłady:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice Liczba podtablic Spróbuj!
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.
Podejście 1: Liczenie podtablic zawierających element max<= K and then subtracting from total subarrays.
Pomysł jest taki, aby podejść do problemu poprzez zliczenie podtablic, których maksymalny element jest mniejszy lub równy k, ponieważ liczenie takich podtablic jest łatwiejsze. Aby znaleźć numer podtablicy, której maksymalny element jest mniejszy lub równy k, usuń wszystkie elementy większe niż K i znajdź numer podtablicy z lewymi elementami.
Gdy znajdziemy powyższą liczbę, możemy odjąć ją od n*(n+1)/2, aby uzyskać wymagany wynik. Zauważ, że może istnieć n*(n+1)/2 możliwych liczb podtablicy dowolnej tablicy o rozmiarze n. Zatem znalezienie liczby podtablicy, której maksymalny element jest mniejszy lub równy K i odjęcie go od n*(n+1)/2 daje nam odpowiedź.
Poniżej implementacja tego podejścia:
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. ?> Wyjście
3
Złożoność czasowa: O(n).
Przestrzeń pomocnicza: O(1)
Podejście 2: Liczenie podtablic mających maksymalny element > K
W tym podejściu po prostu znajdujemy liczbę podtablic, które można utworzyć, włączając element o indeksie i, który jest większy niż K. Zatem, jeśli załóżmy, że arr [ ja ] > K wówczas wszystkie podtablice, w których występuje ten element, będą miały wartość większą niż k, więc po prostu obliczamy wszystkie te podtablice dla każdego elementu większego niż K i dodajemy je w odpowiedzi. Najpierw inicjujemy dwie zmienne lata = 0 zawiera odpowiedź i poprzedni = -1 śledzi to indeks poprzedniego elementu, który był większy niż K.
Aby to zrobić, potrzebujemy trzech wartości dla każdego arr [i] > K.
- Liczba podtablic począwszy od indeksu I . To będzie ( N - ja ) . UWAGA: uwzględniliśmy w tym podtablicę zawierającą pojedynczy element, czyli sam ten element. {arr [ ja ] }
- Liczba podtablic kończących się na tym indeksie I ale indeks początkowy tych podtablic znajduje się po indeksie poprzednie poprzedniego elementu, który był większy niż K, dlaczego to robimy? Ponieważ dla tych elementów musieliśmy już obliczyć naszą odpowiedź, więc nie chcemy liczyć tych samych podtablic więcej niż raz. Zatem ta wartość się pojawi ( ja - poprzedni - 1 ) . UWAGA: W tym przypadku odejmujemy 1, ponieważ policzyliśmy już podtablicę {arr [ i ] } mającą samą siebie jako pojedynczy element. Patrz powyższa uwaga do punktu.
- Liczba podtablic mających indeks początkowy mniejszy niż I ale większy niż poprzednie i indeks końcowy większy niż I . Dlatego wszystkie podtablice, w których arr[i] znajduje się pomiędzy. Możemy to obliczyć, mnożąc powyższe dwie wartości. Powiedzmy, że jako L = ( N - i - 1 ) I R = (i - poprzednia -1 ). Teraz po prostu mnożymy te L i R, ponieważ na każdy 1 indeks po lewej stronie i istnieje indeks R, który może tworzyć różne podtablice, podstawowe rzeczy matematyczne. Więc to się staje L*R. Zauważ, że w wartości L faktycznie odjęliśmy 1. Jeśli tego nie zrobimy, wówczas uwzględnimy indeks i w naszym L*R, co będzie oznaczać, że ponownie uwzględniliśmy podtablice typu numer 1. Patrz punkt 1.
Poniżej implementacja tego podejścia:
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));
Wyjście
12
Złożoność czasowa: O(n).
Podejście 3: Technika przesuwanego okna.
Algorytm:
1. Zainicjuj zmienną lata = 0 zmienna maksymalnyElement = 0 i zmienna liczba = 0 .
2. Iteruj po tablicy, wykonując następujące czynności dla każdego elementu:
A. Jeśli bieżący element, tj. arr[ ja ] jest większa niż bieżące maksimum, zaktualizuj maksimum, tj. Radio = arr ] i zresetuj licznik do 0.
B. Jeśli bieżący element jest mniejszy lub równy bieżącemu maksimum, zwiększ liczbę.
C. Jeśli maxElement jest wtedy większe niż k dodaj liczbę podtablic do ostatecznej odpowiedzi i zaktualizuj plik maxElement do bieżącego elementu.
3. Wróć Ostateczna odpowiedź.
Oto realizacja techniki okna przesuwnego.
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
Wyjście
9
Technika przesuwanego okna została opracowana przez Vaibhav Saroj .
Złożoność czasowa: O( n ).
Złożoność przestrzeni: O( 1 ).