資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告