logo

TechCodeview

Število podnizov, katerih največji element je večji od k

Glede na niz n elementov in celo število k . Naloga je najti število podnizov, ki imajo največji element večji od K.

Primeri:  

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 Število podnizov Poskusite!

Pristop 1: štetje podnizov z največjim številom elementov<= K and then subtracting from total subarrays.

Ideja je pristopiti k problemu s štetjem podnizov, katerih največji element je manjši ali enak k, saj je štetje takih podnizov lažje. Če želite najti število podnizov, katerih največji element je manjši ali enak k, odstranite vse elemente, ki so večji od K, in poiščite število podmatriz z levimi elementi. 



Ko najdemo zgornje število, ga lahko odštejemo od n*(n+1)/2, da dobimo zahtevani rezultat. Upoštevajte, da je lahko n*(n+1)/2 možno število podnizov katerega koli polja velikosti n. Odgovor dobimo tako, da poiščemo število podnizov, katerih največji element je manjši ali enak K, in ga odštejemo od n*(n+1)/2.

Spodaj je izvedba tega pristopa:

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

Izhod 
3

Časovna zahtevnost: O(n).
Pomožni prostor: O(1)

Pristop 2: štetje podnizov z največjim elementom > K

Pri tem pristopu preprosto najdemo število podnizov, ki jih je mogoče oblikovati z vključitvijo elementa pri indeksu i, ki je večji od K. Torej, če predpostavimo arr [ i ] > K potem bodo vse podnize, v katerih je ta element prisoten, imele vrednost, ki je večja od k, zato samo izračunamo vse te podmatriže za vsak element, ki je večji od K, in jih dodamo v odgovor. Najprej inicializiramo dve spremenljivki leta = 0 to vsebuje odgovor in prejšnji = -1 to spremlja indeks prejšnjega elementa, ki je bil večji od K.

Za to potrebujemo le tri vrednosti za vsak arr [ i ] > K .

  1. Število podnizov, začenši z indeksom i . To bo ( N - i ) . OPOMBA: V to smo vključili podmatriko, ki vsebuje en sam element, ki je ta sam element. { arr [ i ] }
  2. Število podnizov, ki se končajo s tem indeksom i vendar je začetni indeks teh podnizov za indeksom prev prejšnjega elementa, ki je bil večji od K, zakaj to počnemo? Ker smo za te elemente morali že izračunati svoj odgovor, tako da ne želimo več kot enkrat šteti istih podnizov. Tako bo ta vrednost nastala ( i - prejšnja - 1 ) . OPOMBA: Pri tem odštejemo 1, ker smo že prešteli podmatriko { arr [ i ] }, ki ima samo sebe kot en element. Glej zgornjo opombo. 
  3. Število podnizov z začetnim indeksom, manjšim od i ampak večji od prev in končni indeks večji od i . Torej vse podnize, v katerih je arr[i] vmes. To lahko izračunamo tako, da pomnožimo zgornji dve vrednosti. Recimo jim kot L = ( N - i - 1 ) in R = (i - prejšnji -1). Zdaj samo pomnožimo ta L in R, ker za vsak 1 indeks na levi strani i obstaja indeks R, ki lahko naredi različne podnize osnovne matematične stvari. Torej to postane L * R. Upoštevajte, da smo tukaj pri vrednosti L dejansko odšteli 1, če tega ne storimo, vključimo indeks i v naš L*R, kar bo pomenilo, da smo znova vključili podnize tipa številka 1. Glej točko 1.    

Spodaj je izvedba tega pristopa:

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

Izhod 
12

Časovna zahtevnost: O(n).

Pristop 3: tehnika drsnega okna.

Algoritem:

1. Inicializirajte spremenljivko leta = 0 spremenljivka maxElement = 0 in spremenljivko štetje = 0 .

2. Iterirajte skozi matriko in za vsak element naredite naslednje:

  a. Če trenutni element, tj. arr[ i ] je večji od trenutnega maksimuma posodobite maksimum, tj. Radio = arr ] in ponastavite štetje na 0.

  b. Če je trenutni element manjši ali enak trenutnemu maksimumu, povečajte število.

  c. če maxElement potem je grtejeter od k dodajte štetje podnizov do končnega odgovora in posodobitev maxElement na trenutni element.

3. Vrni Končni odgovor.

Tukaj je izvedba tehnike drsnega okna.

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

Izhod 
9

Tehnika drsnih oken prispeva Vaibhav Saroj .

Časovna kompleksnost: O( n ).
Prostorska kompleksnost: O( 1 ).

Vadite tukaj Število podnizov .

Ustvari kviz