の配列が与えられると、 n 要素と整数 k 。タスクは、K より大きい最大要素を持つ部分配列の数を見つけることです。
例:
Input : arr[] = {1 2 3} and k = 2.Recommended Practice サブアレイの数 試してみてください!
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.
アプローチ 1: 最大要素を持つ部分配列を数える<= K and then subtracting from total subarrays.
この考え方は、最大要素が k 以下である部分配列を数える方が簡単であるため、そのような部分配列を数えることで問題にアプローチするというものです。最大要素が k 以下である部分配列の数を見つけるには、K より大きいすべての要素を削除し、左側の要素を持つ部分配列の数を見つけます。
上記のカウントが見つかったら、それを n*(n+1)/2 から減算して、必要な結果を得ることができます。サイズ n の任意の配列のサブ配列の数が n*(n+1)/2 になる可能性があることに注意してください。したがって、最大要素が K 以下である部分配列の数を見つけて、それを n*(n+1)/2 から減算すると、答えが得られます。
以下はこのアプローチの実装です。
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. ?> 出力
3
時間計算量: O(n)。
補助スペース: O(1)
アプローチ 2: 最大要素 > K を持つ部分配列を数える
このアプローチでは、単に K より大きいインデックス i の要素を含めることによって形成できる部分配列の数を見つけるだけです。 arr [ i ] > K この場合、この要素が存在するすべての部分配列は k より大きい値を持つことになるため、K より大きい要素ごとにこれらの部分配列をすべて計算し、それらを加算して答えを返します。まず 2 つの変数を初期化します 年 = 0 これには答えが含まれており、 前 = -1 これにより、K より大きい前の要素のインデックスが追跡されます。
これを行うには、 arr[i] > K ごとに 3 つの値が必要なだけです。
- インデックスから始まるサブ配列の数 私 。これは、 ( N - i ) 。 注: ここには、この要素自体である単一の要素を含むサブ配列が含まれています。 {arr[i]}
- このインデックスで終わるサブ配列の数 私 ただし、これらの部分配列の開始インデックスはインデックスの後です 前へ K より大きい前の要素のなぜこれを行うのでしょうか?その要素についてはすでに答えを計算している必要があるため、同じ部分配列を複数回カウントしたくないからです。したがって、この値は次のようになります ( i - 前 - 1) 。 注: ここでは、それ自体を単一の要素として持つ部分配列 { arr [ i ] } を既にカウントしているため、1 を減算します。上記のポイントノートを参照してください。
- 開始インデックスが以下のサブ配列の数 私 しかし、それよりも大きい 前へ 終了インデックスが次より大きい 私 。したがって、arr[i] が間にあるすべてのサブ配列。これは、上記の 2 つの値を乗算することで計算できます。それらを次のように言いましょう L = (N-i-1) そして R = ( i - 前 -1 )。 ここで、これらの L と R を乗算するだけです。i の左側の 1 インデックスごとに、異なる部分配列を基本的な数学にできる R インデックスがあるからです。したがって、これは次のようになります L * R 。ここで、L の val で実際に 1 が減算されていることに注意してください。これを行わない場合は、L*R にインデックス i を含めます。これは、番号 1 タイプの部分配列を再度含めたことを意味します。ポイント 1 を参照してください。
以下はこのアプローチの実装です。
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));
出力
12
時間計算量: O(n)。
アプローチ 3 : スライディング ウィンドウ手法。
アルゴリズム：
1. 変数を初期化する 年 = 0 変数 最大要素 = 0 そして変数 カウント = 0 。
2. 各要素に対して以下を実行して配列を反復処理します。
ａ． 現在の要素の場合、つまり ああ[私] 現在の最大値よりも大きいです。つまり、最大値を更新します。 ラジオ=arr] そしてカウントを0にリセットします。
b. 現在の要素が現在の最大値以下である場合は、カウントを増分します。
c. もし maxElement は k よりも大きいです カウントを追加する サブ配列の最終的な答えと更新 maxElement 現在の要素に。
3. 最終的な答えを返します。
ここではスライディング ウィンドウ手法の実装を示します。
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
出力
9
スライディング ウィンドウ テクニックの提供者は次のとおりです。 ヴァイバブ・サロジ 。
時間計算量: O( n )。
空間の複雑さ: O( 1 )。