数据结构
网络
关系数据库管理系统 (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 次浏览
