数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中统计所有元素都大于 K 的子数组
给定一个整数数组 arr[] 和一个数字 K。目标是统计 arr[] 的所有子数组，使得子数组的所有元素都大于 K 或 K 小于子数组的所有元素。如果数组为 [1,2,3] 且 K 为 1。子数组将为 [2]、[3]、[2,3]。
让我们通过示例来理解。
输入 − arr[] = { 2, 2, 1, 1, 1, 5 }; K=1
输出 − 所有元素都大于 K 的子数组的数量为 − 4
解释 − 子数组将为：[2]、[2]、[5]、[2,2]。每个子数组中的所有元素都大于 1。
输入 − arr[] = { 3,4,5,6 }; K=2
输出 − 所有元素都大于 K 的子数组的数量为 − 10
解释 − 子数组将为 − [3]、[4]、[5]、[6]、[3,4]、[4,5]、[5,6]、[3,4,5]、[4,5,6]、[3,4,5,6]。总数=10。
下面程序中使用的方案如下
我们将使用 for 循环遍历数组。如果当前元素大于 K。则递增计数。否则将计数设置为 0，并将总计设置为 count*(count+1)/2。（用于子数组）。如果最后计数非零。则为剩余子数组的计数添加 count*(count+1)/2。
获取一个数字数组 arr[]。
函数 sub_greater_k(int arr[], int size, int k) 获取数组并返回所有元素都大于 k 的子数组的数量。
将初始计数设置为 0。
我们将使用 for 循环从 i=0 到 i<size 遍历数组。
如果 arr[i]>k 则递增计数。
具有计数（元素 > k）的子数组将为 count*(count+1)/2。将此添加到所有此类子数组的总计中。
最后再次将 count*(count+1)/2 添加到总计中，如果计数非零。
将总计作为结果返回。
示例
#include <bits/stdc++.h>
using namespace std;
int sub_greater_k(int arr[], int size, int k){
int count = 0;
int total = 0;
for (int i = 0; i < size; i++){
if (arr[i] > k){
count++;
}
else{
total += (count) * (count + 1) / 2;
count = 0;
}
}
if(count){
total += (count) * (count + 1) / 2;
}
return total;
}
int main(){
int arr[] = {2, 4, 6, 1, 3, 7, 9 };
int size = sizeof(arr) / sizeof(arr[0]);
int k = 7;
cout<<"Count of subarrays with all elements greater than K are: "<<sub_greater_k(arr, size, k);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count of subarrays with all elements greater than K are: 1
383 次查看
