给定一个由n个元素和一个整数X组成的数组。计算该数组中所有元素小于或等于X的子数组的数量。 例如：
null
Input : arr[] = {1, 5, 7, 8, 2, 3, 9} X = 6Output : 6Explanation : Sub-arrays are {1}, {5}, {2}, {3},{1, 5}, {2, 3}Input : arr[] = {1, 10, 12, 4, 5, 3, 2, 7} X = 9Output : 16
天真的方法 ：一种简单的方法使用两个嵌套循环来生成给定数组的所有子数组，一个循环用来检查子数组的所有元素是否小于或等于X。 时间复杂度：O（n*n*n） 有效的方法 ：一种有效的方法是观察那些所有元素都小于或等于X的子数组的计数。我们可以创建一个0和1的二进制数组，对应于原始数组。如果原始数组中的一个元素小于或等于X，则二进制数组中的对应元素将为1，否则为0。现在，我们的问题是计算这个二进制数组中所有1的子数组的数量。我们还可以看到，对于所有1的数组，其所有子数组将只有1，子数组的总数将是len*（len+1）/2。例如，{1,1,1,1}将有10个子数组。 下面是解决上述问题的完整算法：
- 如上所述，创建原始数组的相应二进制数组。
- 将计数器变量初始化为0，并开始遍历二进制数组，跟踪所有1的子数组的长度
- 通过使用公式n*（n+1）/2，我们可以很容易地计算所有1的数组的子数组数，其中n是所有1的数组的长度。
- 计算所有1的每个子数组的长度，并将计数变量增加长度*（长度+1）/2。我们可以在O（n）时间复杂度下完成这项工作
以下是上述方法的实施情况：
C++
// C++ program to count all sub-arrays which // has all elements less than or equal to X #include <iostream> using namespace std; // function to count all sub-arrays which // has all elements less than or equal to X int countSubArrays( int arr[], int n, int x) { // variable to keep track of length of // subarrays with all 1s int len = 0; // variable to keep track of all subarrays int count = 0; // binary array of same size int binaryArr[n]; // creating binary array for ( int i = 0; i < n; i++) { if (arr[i] <= x) binaryArr[i] = 1; else binaryArr[i] = 0; } // start traversing the binary array for ( int i = 0; i < n; i++) { // once we find the first 1, keep checking // for number of consecutive 1s if (binaryArr[i] == 1) { int j; for (j = i + 1; j < n; j++) if (binaryArr[j] != 1) break ; // calculate length of the subarray // with all 1s len = j - i; // increment count count += (len) * (len + 1) / 2; // initialize i to j i = j; } } return count; } // Driver code int main() { int arr[] = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; int n = sizeof (arr) / sizeof (arr[0]); cout << countSubArrays(arr, n, x); return 0; } |
JAVA
// Java program to count all sub-arrays which // has all elements less than or equal to X import java.io.*; class GFG { // function to count all sub-arrays which // has all elements less than or equal to X static int countSubArrays( int arr[], int n, int x) { // variable to keep track of length of // subarrays with all 1s int len = 0 ; // variable to keep track of all subarrays int count = 0 ; // binary array of same size int binaryArr[] = new int [n]; // creating binary array for ( int i = 0 ; i < n; i++) { if (arr[i] <= x) binaryArr[i] = 1 ; else binaryArr[i] = 0 ; } // start traversing the binary array for ( int i = 0 ; i < n; i++) { // once we find the first 1, keep checking // for number of consecutive 1s if (binaryArr[i] == 1 ) { int j; for (j = i + 1 ; j < n; j++) if (binaryArr[j] != 1 ) break ; // calculate length of the subarray // with all 1s len = j - i; // increment count count += (len) * (len + 1 ) / 2 ; // initialize i to j i = j; } } return count; } // Driver code public static void main(String args[]) { int arr[] = { 1 , 5 , 7 , 8 , 2 , 3 , 9 }; int x = 6 ; int n = arr.length; System.out.println(countSubArrays(arr, n, x)); } } // This code is contributed by Nikita Tiwari. |
Python3
# python 3 program to count all sub-arrays which # has all elements less than or equal to X # function to count all sub-arrays which # has all elements less than or equal to X def countSubArrays(arr, n, x): # variable to keep track of length # of subarrays with all 1s len = 0 # variable to keep track of # all subarrays count = 0 # binary array of same size binaryArr = [ 0 for i in range (n)] # creating binary array for i in range ( 0 , n, 1 ): if (arr[i] < = x): binaryArr[i] = 1 else : binaryArr[i] = 0 # start traversing the binary array for i in range ( 0 , n, 1 ): # once we find the first 1, # keep checking for number # of consecutive 1s if (binaryArr[i] = = 1 ): for j in range (i + 1 , n, 1 ): if (binaryArr[j] ! = 1 ): break # calculate length of the # subarray with all 1s len = j - i # increment count count + = ( len ) * ( int )(( len + 1 ) / 2 ) # initialize i to j i = j return count # Driver code if __name__ = = '__main__' : arr = [ 1 , 5 , 7 , 8 , 2 , 3 , 9 ] x = 6 n = len (arr) print ( int (countSubArrays(arr, n, x))) # This code is contributed by # Surendra_Gangwar |
C#
// C# program to count all sub-arrays which // has all elements less than or equal to X1 using System; class GFG { // function to count all sub-arrays which // has all elements less than or equal // to X static int countSubArrays( int []arr, int n, int x) { // variable to keep track of length // of subarrays with all 1s int len = 0; // variable to keep track of all // subarrays int count = 0; // binary array of same size int []binaryArr = new int [n]; // creating binary array for ( int i = 0; i < n; i++) { if (arr[i] <= x) binaryArr[i] = 1; else binaryArr[i] = 0; } // start traversing the binary array for ( int i = 0; i < n; i++) { // once we find the first 1, keep // checking for number of // consecutive 1s if (binaryArr[i] == 1) { int j; for (j = i + 1; j< n; j++) if (binaryArr[j] != 1) break ; // calculate length of the // subarray with all 1s len = j - i; // increment count count += (len) * (len + 1) / 2; // initialize i to j i = j; } } return count; } // Driver code public static void Main() { int []arr = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; int n = arr.Length; Console.WriteLine( countSubArrays(arr, n, x)); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to count all sub-arrays which // has all elements less than or equal to X // function to count all sub-arrays which // has all elements less than or equal to X function countSubArrays( $arr , $n , $x ) { // variable to keep track of length of // subarrays with all 1s $len = 0; // variable to keep track of all subarrays $coun = 0; // binary array of same size $binaryArr = array ( $n ); // creating binary array for ( $i = 0; $i < $n ; $i ++) { if ( $arr [ $i ] <= $x ) $binaryArr [ $i ] = 1; else $binaryArr [ $i ] = 0; } // start traversing // the binary array for ( $i = 0; $i < $n ; $i ++) { // once we find the first 1, // keep checking for number // of consecutive 1s if ( $binaryArr [ $i ] == 1) { for ( $j = $i + 1; $j < $n ; $j ++) if ( $binaryArr [ $j ] != 1) break ; // calculate length of // the subarray with all 1s $len = $j - $i ; // increment count $coun += ( $len ) * ( $len + 1) / 2; // initialize i to j $i = $j ; } } return $coun ; } // Driver code $arr = array ( 1, 5, 7, 8, 2, 3, 9 ); $x = 6; $n = count ( $arr ); echo countSubArrays( $arr , $n , $x ); // This code is contributed by Sam007 ?> |
Javascript
<script> // javascript program to count all sub-arrays which // has all elements less than or equal to X // function to count all sub-arrays which // has all elements less than or equal to X function countSubArrays(arr , n , x) { // variable to keep track of length of // subarrays with all 1s var len = 0; // variable to keep track of all subarrays var count = 0; // binary array of same size var binaryArr = Array(n).fill(0); // creating binary array for (i = 0; i < n; i++) { if (arr[i] <= x) binaryArr[i] = 1; else binaryArr[i] = 0; } // start traversing the binary array for (i = 0; i < n; i++) { // once we find the first 1, keep checking // for number of consecutive 1s if (binaryArr[i] == 1) { var j; for (j = i + 1; j < n; j++) if (binaryArr[j] != 1) break ; // calculate length of the subarray // with all 1s len = j - i; // increment count count += (len) * (len + 1) / 2; // initialize i to j i = j; } } return count; } // Driver code var arr = [ 1, 5, 7, 8, 2, 3, 9 ]; var x = 6; var n = arr.length; document.write(countSubArrays(arr, n, x)); // This code is contributed by Rajput-Ji </script> |
输出：
6
时间复杂性 ：O（n），其中n是数组中的元素数。 辅助空间 ：O（n）。 另一种方法： 我们可以在不使用额外空间的情况下改进上述解决方案，从而保持时间复杂度O（n）。我们不需要将元素标记为0和1，而是可以跟踪每个此类区域的开始和结束，并在区域结束时更新计数。
C++
// C++ program to count all sub-arrays which // has all elements less than or equal to X #include<bits/stdc++.h> using namespace std; int countSubArrays( int arr[], int x, int n ) { int count = 0; int start = -1, end = -1; for ( int i = 0; i < n; i++) { if (arr[i] < x) { if (start == -1) { //create a new subArray start = i; end = i; } else { // append to existing subarray end=i; } } else { if (start != -1 && end != -1) { // given start and end calculate // all subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } start = -1; end = -1; } } if (start != -1 && end != -1) { // given start and end calculate all // subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } return count; } // Driver code int main() { int arr[] = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; int n = sizeof (arr) / sizeof (arr[0]); cout<< countSubArrays(arr, x, n); //This code is contributed by 29AjayKumar } |
JAVA
// Java program to count all sub-arrays which // has all elements less than or equal to X public class GFG { public static int countSubArrays( int arr[], int x) { int count = 0 ; int start = - 1 , end = - 1 ; for ( int i = 0 ; i < arr.length; i++) { if (arr[i] < x) { if (start == - 1 ) { //create a new subArray start = i; end = i; } else { // append to existing subarray end=i; } } else { if (start != - 1 && end != - 1 ) { // given start and end calculate // all subarrays within this range int length = end - start + 1 ; count = count + ((length * (length + 1 )) / 2 ); } start = - 1 ; end = - 1 ; } } if (start != - 1 && end != - 1 ) { // given start and end calculate all // subarrays within this range int length = end - start + 1 ; count = count + ((length * (length + 1 )) / 2 ); } return count; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 5 , 7 , 8 , 2 , 3 , 9 }; int x = 6 ; System.out.println(countSubArrays(arr, x)); } } |
Python3
# Python3 program to count all sub-arrays which # has all elements less than or equal to X def countSubArrays(arr, x, n ): count = 0 ; start = - 1 ; end = - 1 ; for i in range (n): if (arr[i] < x): if (start = = - 1 ): # create a new subArray start = i; end = i; else : # append to existing subarray end = i; else : if (start ! = - 1 and end ! = - 1 ): # given start and end calculate # all subarrays within this range length = end - start + 1 ; count = count + ((length * (length + 1 )) / 2 ); start = - 1 ; end = - 1 ; if (start ! = - 1 and end ! = - 1 ): # given start and end calculate all # subarrays within this range length = end - start + 1 ; count = count + ((length * (length + 1 )) / 2 ); return count; # Driver code arr = [ 1 , 5 , 7 , 8 , 2 , 3 , 9 ]; x = 6 ; n = len (arr); print (countSubArrays(arr, x, n)); # This code is contributed # by PrinciRaj1992 |
C#
// C# program to count all sub-arrays which // has all elements less than or equal to X using System; class GFG { public static int countSubArrays( int []arr, int x) { int count = 0; int start = -1, end = -1; for ( int i = 0; i < arr.Length; i++) { if (arr[i] < x) { if (start == -1) { //create a new subArray start = i; end = i; } else { // append to existing subarray end=i; } } else { if (start != -1 && end != -1) { // given start and end calculate // all subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } start = -1; end = -1; } } if (start != -1 && end != -1) { // given start and end calculate all // subarrays within this range int length = end - start + 1; count = count + ((length * (length + 1)) / 2); } return count; } // Driver code public static void Main(String[] args) { int []arr = { 1, 5, 7, 8, 2, 3, 9 }; int x = 6; Console.WriteLine(countSubArrays(arr, x)); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program to count all sub-arrays which // has all elements less than or equal to X function countSubArrays(arr, x) { let count = 0; let start = -1, end = -1; for (let i = 0; i < arr.length; i++) { if (arr[i] < x) { if (start == -1) { //create a new subArray start = i; end = i; } else { // append to existing subarray end=i; } } else { if (start != -1 && end != -1) { // given start and end calculate // all subarrays within this range let length = end - start + 1; count = count + parseInt((length * (length + 1)) / 2, 10); } start = -1; end = -1; } } if (start != -1 && end != -1) { // given start and end calculate all // subarrays within this range let length = end - start + 1; count = count + parseInt((length * (length + 1)) / 2, 10); } return count; } let arr = [ 1, 5, 7, 8, 2, 3, 9 ]; let x = 6; document.write(countSubArrays(arr, x)); </script> |
输出：
6
时间复杂性： O（n），其中n是数组中的元素数。 辅助空间： O（1）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
