首页 > 后端开发 > C++ > 计算长度为K的子数组,其平均值超过给定数组的中位数

计算长度为K的子数组,其平均值超过给定数组的中位数

WBOY
发布: 2023-09-02 08:09:13
转载
1474 人浏览过

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

来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板