C++程序 计算数组范围内的平均数
给定一个包含 n 个整数的数组。你需要解决 q 个查询。编写一个程序,在每个查询的新行中打印区间 [l, r] 的平均值向下取整的值。
示例:
输入 : arr[] = {1, 2, 3, 4, 5}
q = 3
0 2
1 3
0 4
输出 : 2
3
3
对于 0 到 2 的区间 (1 + 2 + 3) / 3 = 2
输入 : arr[] = {6, 7, 8, 10}
q = 2
0 3
1 2
输出 : 7
7
Naive Approach: 我们可以为每个查询 l 到 r 运行循环并查找范围内的数字的和和元素数。之后,我们可以为每个查询打印平均值的向下取整的值。
// CPP program to find floor value
// of mean in range l to r
#include <bits/stdc++.h>
using namespace std;
// To find mean of range in l to r
int findMean(int arr[], int l, int r)
{
// Both sum and count are
// initialize to 0
int sum = 0, count = 0;
// To calculate sum and number
// of elements in range l to r
for (int i = l; i <= r; i++) {
sum += arr[i];
count++;
}
// Calculate floor value of mean
int mean = floor(sum / count);
// Returns mean of array
// in range l to r
return mean;
}
// Driver program to test findMean()
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
cout << findMean(arr, 0, 2) << endl;
cout << findMean(arr, 1, 3) << endl;
cout << findMean(arr, 0, 4) << endl;
return 0;
}
输出 :
2
3
3
时间复杂度: O(n*q) ,其中 q 是查询的数量,n 是数组的大小。在上面的代码中,q 是 3,因为 findMean 函数被使用了 3 次。
辅助空间: O(1)
高效方法: 我们可以使用前缀和计算数字的和。prefixSum[i] 表示前 i 个元素的和。因此范围 l 到 r 中数字的和将是 prefixSum[r] – prefixSum[l-1]。范围 l 到 r 中的元素数将是 r – l + 1。因此,我们现在可以在 O(1) 时间内打印范围 l 到 r 的平均值向下取整的值。
// CPP program to find floor value
// of mean in range l to r
#include <bits/stdc++.h>
#define MAX 1000005
using namespace std;
int prefixSum[MAX];
// To calculate prefixSum of array
void calculatePrefixSum(int arr[], int n)
{
// Calculate prefix sum of array
prefixSum[0] =arr[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
// To return floor of mean
// in range l to r
int findMean(int l, int r)
{
if (l == 0)
return floor(prefixSum[r]/(r+1));
// Sum of elements in range l to
// r is prefixSum[r] - prefixSum[l-1]
// Number of elements in range
// l to r is r - l + 1
return floor((prefixSum[r] -
prefixSum[l - 1]) / (r - l + 1));
}
// Driver program to test above functions
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
calculatePrefixSum(arr, n);
cout << findMean(0, 2) << endl;
cout << findMean(1, 3) << endl;
cout << findMean(0, 4) << endl;
return 0;
}
输出:
2
3
3
时间复杂度: O(n+q) ,其中 q 是查询的数量,n 是数组的大小。在上面的代码中,q 是 3,因为 findMean 函数被使用了 3 次。
辅助空间: O(k),其中 k=1000005。