資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學統計平均值超過給定陣列中位數的長度為 K 的子陣列個數
“長度為 K 的子陣列”指的是恰好包含 K 個元素的連續子陣列。理解和處理子陣列對於解決動態規劃、計算幾何和資料分析等領域中的各種問題至關重要。
陣列操作和統計學中的另一個重要概念是中位數。陣列的中位數表示當元素按升序排列時的中間值。如果元素個數為偶數，則中位數是兩個中間值的平均值。與平均值相比，中位數是中心趨勢的穩健度量，因為它不易受極值或異常值的影響。
本文旨在探討確定平均值超過給定陣列中位數的長度為 K 的子陣列個數這一挑戰。透過理解資料集的平均值和中位數之間的關係，我們可以深入研究這一挑戰，並開發有效的技術來解決它。讓我們一起剖析問題陳述，研究關鍵概念，並逐步學習演算法，以高效地在陣列中計算所需的長度為 K 的子陣列。
語法
將陣列中的元素按升序排序。
sort(begin(array), end(array))
宣告一個整數向量。
vectorvec
宣告一個整數陣列。
int arr[]
C++ 中的基本 for 迴圈語法。
for(int i=0; i<size; ++i)
原始碼演算法
讀取輸入陣列及其大小。
計算給定陣列的中位數。
對於每個長度為 K 的子陣列，計算平均值。
將平均值與中位數進行比較。
計算平均值超過中位數的子陣列個數。
方法 1：暴力法
方法 1 是一種直接解決確定平均值超過指定陣列中位數的長度為 K 的子陣列個數的挑戰的方案。首先，對輸入陣列進行排序並計算中位數。然後，程式遍歷所有可能的長度為 K 的子陣列，並透過累加其元素來計算它們的平均值。如果子陣列的平均值超過中位數，則計數器遞增。最後，程式碼返回此類子陣列的數量。
演算法
計算給定陣列的中位數。
迭代所有可能的長度為 K 的子陣列。
計算每個子陣列的平均值。
如果子陣列的平均值大於中位數，則遞增計數器。
示例 1
下面的程式碼遵循文章前面提到的暴力法。它首先對輸入陣列進行排序並計算中位數。然後，它迭代所有可能的長度為 K 的子陣列，並透過累加它們的元素來計算它們的平均值。如果子陣列的平均值大於中位數，則計數器遞增。最後，程式碼返回此類子陣列的數量。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int countSubarrays(vector<int> &arr, int n, int k) {
int count = 0;
double median;
sort(arr.begin(), arr.end());
median = (n % 2 == 0) ? (arr[n/2 - 1] + arr[n/2]) / 2.0 : arr[n/2];
for (int i = 0; i <= n - k; i++) {
double sum = 0;
for (int j = i; j < i + k; j++) {
sum += arr[j];
}
if (sum / k > median) {
count++;
}
}
return count;
}
int main() {
vector<int> arr = {1, 5, 6, 7, 9};
int n = arr.size();
int k = 3;
int result = countSubarrays(arr, n, k);
cout << "Number of K-length subarrays with average exceeding median: " << result << endl;
return 0;
}
輸出
Number of K-length subarrays with average exceeding median: 1
方法 2：最佳化方法
方法 2 是一種改進的方案，用於解決確定平均值超過指定陣列中位數的長度為 K 的子陣列數量的問題。它首先對輸入陣列進行排序並計算中位數。接下來，它計算字首和陣列，該陣列用於確定每個長度為 K 的子陣列的和。該演算法迭代所有可能的長度為 K 的子陣列，使用字首和陣列計算它們的平均值，並將其與中位數進行比較。
如果子陣列的平均值超過中位數，則計數器遞增。最後，程式返回此類子陣列的數量。這種方法比第一種方法更有效率，因為它使用字首和陣列來計算每個長度為 K 的子陣列的和，從而減少了時間複雜度。
演算法
計算給定陣列的中位數。
計算字首和陣列。
迭代所有可能的長度為 K 的子陣列。
使用字首和陣列計算平均值。
如果子陣列的平均值大於中位數，則遞增計數器。
示例 2
該演算法遵循前面描述的最佳化方法。它利用字首和陣列快速計算每個長度為 K 的子集的總和。在對輸入序列進行排序並確定中位數後，計算字首和。然後，程式遍歷所有長度為 K 的子集，使用字首和陣列計算它們的平均值，並將其與中位數進行比較。如果平均值超過中位數，則計數器遞增。最後，程式碼返回此類子集的數量。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int countSubarrays(vector<int> &arr, int n, int k) {
int count = 0;
double median;
sort(arr.begin(), arr.end());
median = (n % 2 == 0) ? (arr[n/2 - 1] + arr[n/2]) / 2.0 : arr[n/2];
vector<int> prefix_sum(n);
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
}
for (int i = 0; i <= n - k; i++) {
double sum = (i == 0) ? prefix_sum[i + k - 1] : prefix_sum[i + k - 1] - prefix_sum[i - 1];
if (sum / k > median) {
count++;
}
}
return count;
}
int main() {
vector<int> arr = {1, 5, 6, 7, 9};
int n = arr.size();
int k = 3;
int result = countSubarrays(arr, n, k);
cout << "Number of K-length subarrays with average exceeding median: " << result << endl;
return 0;
}
輸出
Number of K-length subarrays with average exceeding median: 1
結論
在本文中，我們討論了兩種使用 C++ 統計平均值超過給定陣列中位數的長度為 K 的子陣列個數的方法。第一種方法是暴力法，它迭代所有可能的長度為 K 的子陣列並計算它們的平均值。第二種方法是一種最佳化方法，它使用字首和陣列更有效地計算平均值。兩種程式碼都已提供，可以執行以找到所需的子陣列數量。
94 次瀏覽
