表达式“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 长度子数组并计算它们的平均值。第二种方法是一种优化方法，它使用前缀和数组来更有效地计算平均值。两个代码都已提供，可以执行以查找所需的子数组数量。
