計算長度為K的子數組，其平均值超過給定數組的中位數

表達式「K 長度子陣列」適用於具有恰好 K 個元素的連續子陣列。掌握和使用子數組對於解決動態規劃、計算幾何和數據分析等領域的各種問題至關重要。

陣列運算和統計學中的另一個重要概念是中位數。數組的中位數表示元素按升序排序時位於中間的值。在元素個數為偶數的情況下，中位數是兩個中心值的平均值。中位數構成了集中趨勢的持久衡量標準，因為與平均值相比，它更不容易受到極端值或異常值的影響。

本文試圖研究確定一個給定數組中平均值超過中位數的K長度子數組數量的挑戰。透過理解資料集的平均值和中位數之間的關係，我們可以深入探討這個挑戰，並發展出解決它的高效技術。加入我們，我們將剖析問題陳述，檢查關鍵概念，並透過演算法高效計算數組中所需的K長度子數組的數量。

文法

依升序對陣列中的元素進行排序。

sort(begin(array), end(array))

宣告一個整數向量。

vector<int> vec
</int>

宣告一個整數數組

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是對確定具有平均值超過指定數組中位數的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中文網其他相關文章！