logo

TechCodeview

Apakšbloku skaits, kuru maksimālais elements ir lielāks par k

Ņemot vērā masīvu n elementi un vesels skaitlis k . Uzdevums ir atrast apakšmasīva skaitu, kuras maksimālais elements ir lielāks par K.

Piemēri:  

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 Subarrays grāfs Izmēģiniet to!

1. pieeja: apakšbloku skaitīšana ar maks. elementu<= K and then subtracting from total subarrays.

Ideja ir risināt problēmu, saskaitot apakšgrupas, kuru maksimālais elements ir mazāks vai vienāds ar k, jo šādu apakšgrupu skaitīšana ir vienkāršāka. Lai atrastu apakšmasīva skaitu, kuras maksimālais elements ir mazāks vai vienāds ar k, noņemiet visus elementus, kas ir lielāki par K, un atrodiet apakšmasīva skaitu ar kreisajiem elementiem. 



Kad esam atraduši iepriekš minēto skaitu, mēs varam to atņemt no n*(n+1)/2, lai iegūtu vajadzīgo rezultātu. Ievērojiet, ka jebkuram masīvam, kura izmērs ir n, var būt n*(n+1)/2 iespējamais apakšmasīva skaits. Tātad, atrodot apakšgrupas skaitu, kuras maksimālais elements ir mazāks vai vienāds ar K, un atņemot to no n*(n+1)/2, mēs iegūstam atbildi.

Tālāk ir sniegta informācija par šīs pieejas īstenošanu.

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. ?>

Izvade 
3

Laika sarežģītība: O(n).
Palīgtelpa: O(1)

2. pieeja: apakšbloku skaitīšana, kuru maksimālais elements ir > K

Šajā pieejā mēs vienkārši atrodam apakšbloku skaitu, ko var izveidot, iekļaujot indeksā i elementu, kas ir lielāks par K. Tāpēc pieņemsim, ka arr [i] > K tad visiem apakšblokiem, kuros atrodas šis elements, būs vērtība, kas ir lielāka par k, tāpēc mēs vienkārši aprēķinām visas šīs apakšgrupas katram elementam, kas ir lielāks par K, un pievienosim tos kā atbildi. Vispirms inicializējam divus mainīgos gadi = 0 tas satur atbildi un iepriekšējā = -1 tas seko iepriekšējā elementa indeksam, kas bija lielāks par K.

Lai to izdarītu, mums ir vajadzīgas trīs vērtības katram arr [i]> K.

  1. Apakšbloku skaits, sākot no indeksa i . Šis būs ( N - i ) . PIEZĪME. Mēs esam iekļāvuši apakšgrupu, kurā ir viens elements, kas ir pats elements. {arr [i]}
  2. Apakšbloku skaits, kas beidzas ar šo indeksu i bet šo apakšgrupu sākuma indekss ir pēc indeksa iepriekj no iepriekšējā elementa, kas bija lielāks par K, kāpēc mēs to darām? Tā kā šiem elementiem mums jau ir jābūt aprēķinājušiem savu atbildi, lai mēs negribētu skaitīt vienus un tos pašus apakšgrupas vairāk nekā vienu reizi. Tātad šī vērtība būs ( i - iepriekšējais - 1) . PIEZĪME. Šajā gadījumā mēs atņemam 1, jo mēs jau esam saskaitījuši apakšgrupu { arr [ i ] }, kurai ir viens elements. Skatīt iepriekš punkta piezīmi. 
  3. To apakšgrupu skaits, kuru sākuma indekss ir mazāks par i bet lielāks par iepriekj un beigu indekss lielāks par i . Tāpēc visas apakšgrupas, kurās arr[i] atrodas starp tām. To mēs varam aprēķināt, reizinot iepriekš minētās divas vērtības. Teiksim tos kā L = ( N - i - 1 ) un R = ( i - iepriekš -1). Tagad mēs vienkārši reizinām šos L un R, jo katram 1 indeksam i kreisajā pusē ir R indekss, kas var veidot dažādus apakšgrupas par pamata matemātikas lietu. Tātad tas kļūst L*R. Ievērojiet šeit val no L mēs faktiski esam atņēmuši 1, ja mēs to nedarām, tad mēs iekļaujam indeksu i savā L*R, kas nozīmē, ka esam atkal iekļāvuši 1. tipa apakšgrupas. Skatīt 1. punktu.    

Tālāk ir sniegta informācija par šīs pieejas īstenošanu.

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));

Izvade 
12

Laika sarežģītība: O(n).

3. pieeja: bīdāmo logu tehnika.

Algoritms:

1. Inicializējiet mainīgo gadi = 0 mainīgais maxElement = 0 un mainīgais skaits = 0 .

2. Atkārtojiet masīvu, katram elementam veicot šādas darbības:

  a. Ja pašreizējais elements t.i. arr[i] ir lielāks par pašreizējo maksimālo atjaunināšanas maksimumu, t.i. Radio = arr] un atiestatiet skaitu uz 0.

  b. Ja pašreizējais elements ir mazāks vai eual līdz pašreizējam maksimumam, palieliniet skaitu.

  c. Ja maxElement ir grteaters par k tad pievienot skaitu apakšrindu, lai sniegtu galīgo atbildi un atjauninātu maxElement uz pašreizējo elementu.

3. Atgriezties Galīgā atbilde.

Lūk, bīdāmo logu tehnikas ieviešana.

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

Izvade 
9

Bīdāmo logu tehniku ​​sniedz Vaibhavs Sarojs .

Laika sarežģītība: O( n ).
Telpas sarežģītība: O( 1 ).

Trenējies šeit Subarrays grāfs .

Izveidojiet viktorīnu