表達式「K 長度子陣列」適用於具有恰好 K 個元素的連續子陣列。掌握和使用子數組對於解決動態規劃、計算幾何和數據分析等領域的各種問題至關重要。
陣列運算和統計學中的另一個重要概念是中位數。數組的中位數表示元素按升序排序時位於中間的值。在元素個數為偶數的情況下，中位數是兩個中心值的平均值。中位數構成了集中趨勢的持久衡量標準，因為與平均值相比，它更不容易受到極端值或異常值的影響。
本文試圖研究確定一個給定數組中平均值超過中位數的K長度子數組數量的挑戰。透過理解資料集的平均值和中位數之間的關係，我們可以深入探討這個挑戰，並發展出解決它的高效技術。加入我們，我們將剖析問題陳述，檢查關鍵概念，並透過演算法高效計算數組中所需的K長度子數組的數量。
文法
依升序對陣列中的元素進行排序。
sort(begin(array), end(array))
登入後複製
宣告一個整數向量。
vector<int> vec
</int>
登入後複製
宣告一個整數數組
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是對確定具有平均值超過指定數組中位數的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 長度子數組併計算它們的平均值。第二種方法是一種最佳化方法，它使用前綴和陣列來更有效地計算平均值。兩個代碼都已提供，可以執行以查找所需的子數組數量。
以上是計算長度為K的子數組，其平均值超過給定數組的中位數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
