计算长度为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中文网其他相关文章！