数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用 C++ 统计子数组个数，要求子数组元素的平均值大于数组中其余元素的平均值
给定一个包含正整数的数组 arr[]。目标是找到 arr[] 的子数组数量，这些子数组的元素平均值大于不在其中的 arr[] 中其余元素的平均值。
例如
输入
arr[ ] = { 3, 2, 4 }输出
Count of number of sub-arrays such that the average of elements present in the sub−array is greater than that do not present in the sub−array are: 2
解释
The subarrays are − [ 3 ], [ 2 ], [ 4 ], [ 3,2 ], [ 2,4 ], [ 3,2,4 ]. Average of [ 4 ] is 4 which is more than the average of [ 2,3 ]. Average of [ 3,2,4 ] is 3 which is more than the average of [ ]
输入
arr[ ] = { 3, 3, 3 }输出
Count of number of sub−arrays such that the average of elements present in the sub−array is greater than that do not present in the sub−array are: 1
解释
The subarrays are − [ 3 ], [ 3 ], [ 3 ], [ 3,3 ], [ 3,3 ], [ 3,3,3 ]. Average of [ 3,3,3 ] is 3 which is more than the average of [ ]
以下程序中使用的算法如下 −
在这个算法中，创建一个前缀和数组，它将把元素的和存储到索引 i 的 new_arr[i] 中。现在我们有了直到前一个元素的和，然后计算直到 arr[i] 的和以及元素数量为 j−i+1，并计算平均值。
将数组 arr[] 作为输入。
函数 count(int arr[], int size) 获取 arr[] 并返回子数组的数量，这样子数组中元素的平均值就大于不在子数组中的元素的平均值。
获取一个数组 new_arr[size] 来存储直到前一个索引元素的和。
从 i=0 到 i<size 遍历并用 new_arr[i−1]+arr[i−1] 设置 new_arr[i]。
现在使用两个 for 循环遍历 new_arr[]。
现在计算 total_1 为前一个子数组的和。以及其中的元素为 count_1。
计算 total_2 为下一个子数组的和以及其中的元素为 count_2。
计算平均值，check_1 = total_1 / count_1; 和 check_2 = total_2 / count_2;
如果平均值 check_1 > check_2，则递增计数。
在 for 循环结束时，返回计数作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
int count(int arr[], int size){
int count = 0;
int new_size = size + 1;
int new_arr[new_size] = { 0 };
for (int i = 1; i < new_size; i++){
new_arr[i] = new_arr[i − 1] + arr[i − 1];
}
for (int i = 1; i < new_size; i++){
for (int j = i; j < new_size; j++){
int total_1 = new_arr[j] − new_arr[i − 1];
int count_1 = j − i + 1;
int total_2 = new_arr[size] − total_1;
int count_2 = 0;
if((size − count_1) == 0){
count_2 = 1;
} else {
count_2 = size − count_1;
}
int check_1 = total_1 / count_1;
int check_2 = total_2 / count_2;
if (check_1 > check_2){
count++;
}
}
}
return count;
}
int main(){
int arr[] = { 2, 6, 2, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of number of sub−arrays such that the average of elements present in
the sub−array "<< "is greater than that not present in the sub−array are: "<<count(arr, size);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count the number of sub−arrays such that the average of elements present in the subarrayis greater than that not present in the sub-array are: 6
更新于：2021年1月5日
153 次查看
广告