Bir dizi göz önüne alındığında N elemanlar ve bir tamsayı k . Görev, maksimum elemanı K'dan büyük olan alt dizinin sayısını bulmaktır.
Örnekler:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice Alt Dizilerin Sayısı Deneyin!
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.
Yaklaşım 1: Maksimum öğeye sahip Alt Dizileri Sayma<= K and then subtracting from total subarrays.
Buradaki fikir, soruna maksimum elemanı k'den küçük veya ona eşit olan alt dizileri sayarak yaklaşmak, çünkü bu tür alt dizileri saymak daha kolaydır. Maksimum elemanı k'den küçük veya k'ye eşit olan alt dizi sayısını bulmak için K'den büyük olan tüm elemanları kaldırın ve sol elemanların bulunduğu alt dizi sayısını bulun.
Yukarıdaki sayımı bulduğumuzda, gerekli sonucu elde etmek için bunu n*(n+1)/2'den çıkarabiliriz. n boyutunda herhangi bir dizide n*(n+1)/2 olası sayıda alt dizi olabileceğini gözlemleyin. Yani maksimum elemanı K'den küçük veya ona eşit olan alt dizi sayısını bulup bunu n*(n+1)/2'den çıkarmak bize cevabı verir.
Aşağıda bu yaklaşımın uygulanması yer almaktadır:
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. ?> Çıkış
3
Zaman Karmaşıklığı: O(n).
Yardımcı Alan: O(1)
Yaklaşım 2: Maksimum elemanı > K olan Alt Dizileri Sayma
Bu yaklaşımda sadece i indeksine K'den büyük bir öğe dahil edilerek oluşturulabilecek alt dizilerin sayısını buluyoruz. dizi [ i ] > K o zaman bu elemanın mevcut olduğu tüm alt diziler k'den büyük bir değere sahip olacaktır, dolayısıyla K'dan büyük her eleman için tüm bu alt dizileri hesaplıyoruz ve yanıt olarak bunları topluyoruz. İlk önce iki değişkeni başlatıyoruz yıl = 0 bu cevap içerir ve önceki = -1 bu, K'den büyük olan önceki öğenin indeksini takip eder.
Bunu yapmak için her arr [ i ] > K için yalnızca üç değere ihtiyacımız var.
- Dizinden başlayarak alt dizilerin sayısı Ben . Bu olacak (N-i) . NOT: Buna, bu öğenin kendisi olan tek öğeyi içeren alt diziyi dahil ettik. { dizi [ ben ] }
- Bu dizinde biten alt dizilerin sayısı Ben ancak bu alt dizilerin başlangıç dizini dizinden sonradır önceki Önceki elemanın K'den büyük olması nedeniyle bunu neden yapıyoruz? Çünkü bu öğeler için cevabımızı zaten hesaplamış olmamız gerekir, bu nedenle aynı alt dizileri birden fazla saymak istemiyoruz. Yani bu değer ortaya çıkacak ( i - önceki - 1 ) . NOT: Burada 1 çıkarıyoruz çünkü zaten kendisi tek eleman olan bir { arr [ i ] } alt dizisini saymıştık. Yukarıdaki nokta notuna bakın.
- Başlangıç indeksi şundan küçük olan alt dizilerin sayısı: Ben ama ondan daha büyük önceki ve bitiş indeksi şundan büyük: Ben . Bu nedenle arr[i]'nin aralarında olduğu tüm alt diziler. Bunu iki değerin üzerini çarparak hesaplayabiliriz. Bunları şöyle söyleyelim L = ( N - i - 1 ) Ve r = ( i - önceki -1 ). Şimdi sadece bu L ve R'yi çarpıyoruz çünkü i'nin sol tarafındaki her 1 indeks için, farklı alt dizileri temel matematik meselesi haline getirebilecek R indeksi vardır. Yani bu olur L*R. Burada L'nin değerinde aslında 1 çıkardığımıza dikkat edin, eğer bunu yapmazsak o zaman L*R'ye i indeksini dahil ederiz, bu da tekrar 1 numaralı tip alt dizileri dahil ettiğimiz anlamına gelir. 1. noktaya bakın.
Aşağıda bu yaklaşımın uygulanması yer almaktadır:
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));
Çıkış
12
Zaman Karmaşıklığı: O(n).
Yaklaşım 3: Kayar Pencere Tekniği.
Algoritma:
1. Bir değişkeni başlat yıl = 0 bir değişken maksimumElement = 0 ve bir değişken sayım = 0 .
2. Her öğe için aşağıdakileri yaparak diziyi yineleyin:
A. Geçerli öğe yani. varış[ ben ] mevcut maksimum güncellemeden daha büyük, yani maksimum Radyo = arr ] ve sayımı 0'a sıfırlayın.
B. Geçerli öğe geçerli maksimum değerden küçükse veya ona eşitse sayımı artırın.
C. Eğer maksimumElement o halde k'den daha büyüktür sayım ekle son cevaba kadar alt dizilerin sayısı ve güncellenmesi maksimumElement mevcut öğeye.
3. Son yanıtı döndür.
İşte Kayar Pencere Tekniğinin uygulanışı.
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
Çıkış
9
Kayar Pencere Tekniğinin katkıları: Vaibhav Saroj .
Zaman Karmaşıklığı: O(n).
Uzay Karmaşıklığı: O( 1 ).