数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中数组范围的平均值
在这个问题中，我们给定一个包含 n 个整数的数组和一些 m 个查询。我们的任务是创建一个程序，计算查询给定范围内平均值的整数部分（向下取整）。
让我们举个例子来理解这个问题，
输入 −
array = {5, 7, 8, 9, 10}
m = 2; [0, 3], [2, 4]输出 −
7 9
为了解决这个问题，我们有两种方法，一种是直接方法，另一种是使用前缀和。
在直接方法中，对于每个查询，我们将从范围的起始索引循环到结束索引。并将数组的所有整数相加并除以计数。这种方法可以正常工作并打印结果，但不是一种有效的方法。
使用 prefixSum
在这种方法中，我们将计算前缀和数组，该数组将存储数组中直到第 i 个索引的所有元素的总和，即 prefixSum(4) 是直到索引 4 的所有元素的总和。
现在，使用此 prefixSum 数组，我们将使用以下公式计算每个查询的平均值：
Mean = prefixSum[upper] - prefixSum(lower-1) / upper-lower+1
Upper 和 lower 是查询中给定的索引。如果 lower = 0，则 prefixSum(lower-1) = 0。
示例
程序说明我们解决方案的工作原理，
#include <iostream>
#define MAX 100
using namespace std;
int prefixSum[MAX];
void initialisePrefixSum(int arr[], int n) {
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int queryMean(int l, int r) {
int mean;
if (l == 0)
mean =(prefixSum[r]/(r+1));
else
mean =((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1));
return mean;
}
int main() {
int arr[] = {5, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
initialisePrefixSum(arr, n);
cout<<"Mean in 1st query: "<<queryMean(1, 4)<<endl;
cout<<"Mean in 2st query: "<<queryMean(2, 4)<<endl;
return 0;
}输出
Mean in 1st query: 8 Mean in 2st query: 9
更新于: 2020-06-03
370 次查看
广告