logo

TechCodeview

Conteggio di sottoarray il cui elemento massimo è maggiore di k

Data una serie di N elementi e un numero intero k . Il compito è trovare il conteggio del sottoarray che ha un elemento massimo maggiore di K.

Esempi:  

Input : arr[] = {1 2 3} and k = 2.  
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.
Recommended Practice Conteggio dei sottoarray Provalo!

Approccio 1: conteggio dei sottoarray con elemento massimo<= K and then subtracting from total subarrays.

L'idea è di affrontare il problema contando i sottoarray il cui elemento massimo è inferiore o uguale a k poiché contare tali sottoarray è più semplice. Per trovare il numero di sottoarray il cui elemento massimo è inferiore o uguale a k, rimuovi tutti gli elementi maggiori di K e trova il numero di sottoarray con gli elementi a sinistra. 



Una volta trovato il conteggio sopra, possiamo sottrarlo da n*(n+1)/2 per ottenere il risultato richiesto. Osservare che può esserci n*(n+1)/2 numero possibile di sottoarray di qualsiasi array di dimensione n. Quindi trovare il numero di sottoarray il cui elemento massimo è inferiore o uguale a K e sottrarlo da n*(n+1)/2 ci dà la risposta.

Di seguito è riportata l’implementazione di questo approccio:

C++ 
// C++ program to count number of subarrays // whose maximum element is greater than K. #include    using namespace std; // Return number of subarrays whose maximum // element is less than or equal to K. 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); } // Driven Program int main() {  int arr[] = { 1 2 3 };  int k = 2;  int n = sizeof(arr) / sizeof(arr[0]);  cout << countSubarray(arr n k);  return 0; }
Java 
// 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.
Python3 
# 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# 
// 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.
JavaScript 
<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 
 // 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. ?>

Produzione 
3

Complessità temporale: O(n).
Spazio ausiliario: O(1)

Approccio 2: conteggio dei sottoarray con elemento massimo > K

In questo approccio troviamo semplicemente il conteggio dei sottoarray che possono essere formati includendo un elemento nell'indice i che è maggiore di K. Pertanto se supponiamo arr [i] > K quindi tutti i sottoarray in cui è presente questo elemento avranno un valore maggiore di k, quindi calcoliamo semplicemente tutti questi sottoarray per ogni elemento maggiore di K e li aggiungiamo in risposta. Innanzitutto inizializziamo due variabili anni = 0 questo contiene la risposta e precedente = -1 questo tiene traccia dell'indice dell'elemento precedente che era maggiore di K.

Per fare questo abbiamo solo bisogno di tre valori per ogni arr [ i ] > K .

  1. Numero di sottoarray a partire dall'indice io . Questo sarà (N-i) . NOTA: in questo abbiamo incluso il sottoarray contenente il singolo elemento che è questo elemento stesso. {arr[i]}
  2. Numero di sottoarray che terminano con questo indice io ma l'indice iniziale di questi sottoarray è dopo l'indice prec dell'elemento precedente che era maggiore di K perché lo facciamo? Perché per quegli elementi dobbiamo aver già calcolato la nostra risposta, quindi non vogliamo contare gli stessi sottoarray più di una volta. Quindi questo valore diventerà realtà ( i - precedente - 1) . NOTA: In questo sottraiamo 1 perché abbiamo già contato un sottoarray { arr [ i ] } avente se stesso come singolo elemento. Vedi la nota sopra. 
  3. Numero di sottoarray con indice iniziale inferiore a io ma maggiore di prec e indice finale maggiore di io . Pertanto tutti i sottoarray in cui arr[i] si trova nel mezzo. Questo possiamo calcolarlo moltiplicando i due valori sopra indicati. Diciamoli come L = ( N - i - 1 ) E R = ( i - precedente -1 ). Ora moltiplichiamo semplicemente questi L e R perché per ogni indice sul lato sinistro di i ci sono indici R che possono creare diversi sottoarray di matematica di base. Quindi questo diventa L*R. Nota qui in val di L abbiamo effettivamente sottratto 1 se non lo facciamo, includiamo l'indice i nel nostro L*R, il che significa che abbiamo incluso nuovamente i sottoarray di tipo numero 1. Vedi punto 1.    

Di seguito è riportata l’implementazione di questo approccio:

C++ 
// C++ program to count number of subarrays // whose maximum element is greater than K. #include    using namespace std; long long countSubarray(int arr[] int n int k) {  long 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 ) * 1LL * ( i - prev - 1 ) ; //subarrays having index i element in between.  prev = i; // updating prev  }  }  return ans; } // Driven Program int main() {  int arr[] = { 4 5 1 2 3 };  int k = 2;  int n = sizeof(arr) / sizeof(arr[0]);  cout << countSubarray(arr n k);  return 0; } // This Code is contributed by Manjeet Singh.
Java 
// 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
Python3 
# 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# 
// 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 
// 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));

Produzione 
12

Complessità temporale: O(n).

Approccio 3: Tecnica della finestra scorrevole.

Algoritmo:

1. Inizializza una variabile anni = 0 una variabile elemento massimo = 0 e una variabile conteggio = 0 .

2. Scorrere l'array effettuando quanto segue per ciascun elemento:

  UN. Se l'elemento corrente, ad es. arr[i] è maggiore del massimo corrente aggiorna il massimo, ad es. La radio = arr] e resettare il conteggio a 0.

  B. Se l'elemento corrente è inferiore o uguale al massimo corrente, incrementare il conteggio.

  C. Se maxElemento è maggiore di k allora aggiungi conteggio di sottoarray per la risposta finale e aggiornare il file maxElemento all'elemento corrente.

3. Ritorno Risposta finale.

Ecco l'implementazione della tecnica della finestra scorrevole.

C++ 
#include    using namespace std; 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;  }  }  return ans; } int main() {  int arr[] = {1 2 3 4};  int k = 1;  int n = sizeof(arr) / sizeof(arr[0]);  cout << countSubarray(arr n k);  return 0; } // This code is contributed by Vaibhav Saroj
C 
#include  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; } int main() {  int arr[] = {1 2 3 4};  int k = 1;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%dn' countSubarray(arr n k));  return 0; } // This code is contributed by Vaibhav Saroj
Java 
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
Python3 
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
C# 
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
JavaScript 
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

Produzione 
9

La tecnica della finestra scorrevole è un contributo di Vaibhav Saroj .

Complessità temporale: O( n ).
Complessità spaziale: O( 1 ).

Fai pratica qui Conteggio dei sottoarray .

Crea quiz