数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中统计元素小于等于 X 的子数组数量
给定一个包含整数的数组 arr[] 和一个变量 X。目标是统计 arr[] 的所有子数组，使得每个子数组仅包含小于或等于 X 的元素。例如，如果数组为 [1,2,3] 且 X=2，则子数组将为 [1]、[2] 和 [1,2]
让我们通过示例来理解。
输入 − arr[] = { 4,3,2,1,6 }; X=3
输出 − 元素小于或等于 X 的子数组数量为 − 6
说明 − 子数组将为 −
[3], [2], [1], [3,2], [2,1], [3,2,1]
输入 − arr[] = { 3,6,2,7,1,8,5 }; X=5
输出 − 元素小于或等于 X 的子数组数量为 − 4
说明 − 子数组将为 −
[3], [2], [1], [5]
下面程序中使用的方案如下
我们正在创建一个与原始数组 arr[] 大小相同的二进制数组 temp_arr[]。如果相应的 arr[i] 小于或等于 X，则此二进制数组将为 1，否则为 0。现在遍历 temp_arr[] 并检查连续的 1（arr[] 中小于 X 的元素）。将每个此类子数组的长度存储在 temp 中。对于长度为 temp 的数组。子数组总数将为 temp*(temp+1)/2。将其添加到总计数中，并继续到 temp_arr[] 的末尾。
获取数组 arr[] 和变量 X。
函数 sub_X(int arr[], int size, int x) 获取数组和 x 并返回仅包含小于或等于 x 的元素的子数组的数量。
获取临时变量 temp 和此类子数组的最终总数作为 count。
获取长度与 arr[] 相同的二进制数组 temp_arr[]。
我们将使用 for 循环从 i=0 到 i<size 遍历数组 arr[]。
对于每个元素 arr[i]<=x，将 temp_arr[i] 设置为 1，否则为 0。
使用 for 循环遍历 temp_arr[]。
如果任何元素 temp_arr[i] == 1。然后使用从当前索引 i 到 temp_arr[temp_2]（temp_2=i+1；temp_2<size）为 1 的子循环进行遍历。如果为 0，则中断子循环。
所有 1 的子数组的计数将为 temp= temp_2-i。
此子数组包含所有 1，这意味着 arr[i] 中的所有元素都 <= x。子数组总数将为 temp_3= temp*(temp+1)/2。
在两次遍历结束时，count 将包含 arr 中所有子数组的总数，这些子数组的数字小于或等于 x。
示例
#include <iostream>
using namespace std;
int sub_X(int arr[], int size, int x){
int count = 0, temp = 0;
int temp_arr[size];
for (int i = 0; i < size; i++){
if (arr[i] <= x){
temp_arr[i] = 1;
}
else{
temp_arr[i] = 0;
}
}
for (int i = 0; i < size; i++){
if (temp_arr[i] == 1){
int temp_2;
for(temp_2 = i + 1; temp_2 < size; temp_2++){
if(temp_arr[temp_2] != 1){
break;
}
}
temp = temp_2 - i;
int temp_3 = (temp) * (temp + 1)/2;
count = count + temp_3;
i = temp_2;
}
}
return count;
}
int main(){
int arr[] = { 2, 6, 1, 10, 5, 3 };
int x = 4;
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of sub-arrays which have elements less than or equal to X are: "<<sub_X(arr, size, x);
return 0;
}输出
如果我们运行上述代码，它将生成以下输出：
Count of sub-arrays which have elements less than or equal to X are: 3
251 次浏览
