Med tanke på en mängd n element och ett heltal k . Uppgiften är att hitta antalet för subarrayen som har ett maximalt element större än K.
Exempel:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice Antal subarrayer Prova!
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.
Tillvägagångssätt 1: Räkna delarrayer med max element<= K and then subtracting from total subarrays.
Tanken är att närma sig problemet genom att räkna subarrayer vars maximala element är mindre än eller lika med k eftersom det är lättare att räkna sådana subarrayer. För att hitta antalet subarray vars maximala element är mindre än eller lika med k ta bort alla element som är större än K och hitta antalet subarray med de vänstra elementen.
När vi har hittat ovanstående räkning kan vi subtrahera det från n*(n+1)/2 för att få vårt önskade resultat. Observera att det kan finnas n*(n+1)/2 möjliga antal underarrayer av vilken array som helst med storlek n. Så genom att hitta antalet undermatris vars maximala element är mindre än eller lika med K och subtrahera det från n*(n+1)/2 får vi svaret.
Nedan följer implementeringen av detta tillvägagångssätt:
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. ?> Produktion
3
Tidskomplexitet: O(n).
Hjälputrymme: O(1)
Tillvägagångssätt 2: Räkna delarrayer med maxelement > K
I detta tillvägagångssätt hittar vi helt enkelt antalet delmatriser som kan bildas genom att inkludera ett element vid index i som är större än K. Därför om antar vi arr [i] > K då kommer alla subarrayer där detta element finns att ha ett värde som är större än k så vi beräknar bara alla dessa subarrays för varje element som är större än K och adderar dem som svar. Vi initialiserar först två variabler år = 0 detta innehåller svar och föregående = -1 detta håller reda på index för föregående element som var större än K.
För att göra detta behöver vi bara tre värden för varje arr [i] > K.
- Antal undermatriser från indexet i . Detta kommer att bli ( N - i ) . OBS: I detta har vi inkluderat den delmatris som innehåller ett enda element som är detta element i sig. { arr [i] }
- Antal undermatriser som slutar på detta index i men startindexet för dessa subarrayer är efter indexet föregående av föregående element som var större än K varför gör vi detta? För för dessa element måste vi redan ha beräknat vårt svar så vi vill inte räkna samma subarrayer mer än en gång. Så detta värde kommer att bli ( i - föregående - 1) . OBS: I detta subtraherar vi 1 eftersom vi redan har räknat en delmatris { arr [ i ] } som har sig själv som ett enda element. Se punktanteckningen ovan.
- Antal undermatriser med startindex mindre än i men större än föregående och slutindex större än i . Därför alla subarrayer där arr[i] är mellan. Detta kan vi beräkna genom att multiplicera ovanför två värden. Låt oss säga dem som L = ( N - i - 1 ) och R = (i - föregående -1). Nu multiplicerar vi bara dessa L och R, för för varje 1 index på vänster sida av i finns det R-index som kan göra olika subarrayer till grundläggande matematik. Så det här blir L*R. Lägg märke till att här i valet av L har vi faktiskt subtraherat 1 om vi inte gör detta så inkluderar vi index i i vår L*R vilket betyder att vi har inkluderat nummer 1 typ subarrays igen. Se punkt 1.
Nedan följer implementeringen av detta tillvägagångssätt:
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));
Produktion
12
Tidskomplexitet: O(n).
Tillvägagångssätt 3: Teknik för skjutfönster.
Algoritm:
1. Initiera en variabel år = 0 en variabel maxElement = 0 och en variabel räkna = 0 .
2. Iterera genom arrayen och gör följande för varje element:
a. Om det aktuella elementet dvs. arr[i] är större än nuvarande maximala uppdatering det maximala dvs. Radion = arr ] och återställ räkningen till 0.
b. Om det aktuella elementet är mindre än eller eual till det nuvarande maximivärdet, öka antalet.
c. Om maxElement är grteare än k då lägga till räkning av subarrays till slutligt svar och uppdatera maxElement till nuvarande element.
3. Returnera Slutligt svar.
Här är implementeringen av Sliding window-tekniken.
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
Produktion
9
Skjutfönstertekniken bidrar med Vaibhav Saroj .
Tidskomplexitet: O( n ).
Rymdkomplexitet: O( 1 ).