
表达式“K 长度子数组”适用于具有恰好 K 个元素的连续子数组。掌握和使用子数组对于解决动态规划、计算几何和数据分析等领域的各种问题至关重要。
数组操作和统计中的另一个重要概念是中位数。数组的中位数表示元素按升序排序时位于中间的值。在元素个数为偶数的情况下,中位数是两个中心值的平均值。中位数构成了集中趋势的持久衡量标准,因为与平均值相比,它更不容易受到极端值或异常值的影响。
本文试图研究确定一个给定数组中平均值超过中位数的K长度子数组数量的挑战。通过理解数据集的平均值和中位数之间的关系,我们可以深入探讨这个挑战,并开发出解决它的高效技术。加入我们,我们将剖析问题陈述,检查关键概念,并通过算法高效计算数组中所需的K长度子数组的数量。
语法
按升序对数组中的元素进行排序。
sort(begin(array), end(array))
声明一个整数向量。
vector<int> vec </int>
声明一个整数数组
int arr[]
C++ 中的基本 for 循环语法。
for(int i=0; i<size><h3>源代码的算法</h3>
<ul class="list">
<li><p>读取输入数组及其大小。</p></li>
<li><p>计算给定数组的中位数。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/ai/2540" title="Phind"><img
src="https://img.php.cn/upload/ai_manual/001/246/273/176907429828304.png" alt="Phind" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/ai/2540" title="Phind" class="overflowclass">Phind</a>
<p class="overflowclass">一款AI开发辅助工具,主要用于Phind 是一款专为开发人员创建的AI搜索引擎,可以快速有效地找到技术查询答案,适合需要提升相关任务效率的用户。</p>
</div>
<a rel="nofollow" href="/ai/2540" title="Phind" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div></li>
<li><p>对于每个长度为K的子数组,计算平均值。</p></li>
<li><p>将平均值与中位数进行比较。</p></li>
<li><p>统计平均值超过中位数的子数组。</p></li>
</ul>
<h2>方法 1:暴力破解</h2>
<p>方法 1 构成了一个简单的解决方案,用于解决确定平均值超过指定数组中位数的 K 长度子数组的数量的挑战。最初,对输入数组进行排序并计算中位数。随后,程序遍历所有可行的 K 长度子数组,并通过聚合它们的分量来计算它们的平均值。如果子数组的平均值超过中位数,则计数会增加。最后,代码返回此类子数组的数量。</p>
<h3>算法</h3>
<ul class="list">
<li><p>计算给定数组的中位数。</p></li>
<li><p>迭代所有可能的 K 长度子数组。</p></li>
<li><p>计算每个子数组的平均值。</p></li>
<li><p>如果子数组的平均值大于中位数,则增加计数。</p></li>
</ul>
<h3>示例 1</h3>
<p>下面的代码遵循本文前面提到的强力方法。它首先对输入数组进行排序并计算中位数。然后,它迭代所有可能的 K 长度子数组,并通过对它们的元素求和来计算它们的平均值。如果子数组的平均值大于中位数,则计数会递增。最后,代码返回此类子数组的计数。</p>
<pre class="brush:cpp;toolbar:false;">#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 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 <h3>输出</h3>
<pre class="brush:php;toolbar:false;">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 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 <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Number of K-length subarrays with average exceeding median: 1
结论
在本文中,我们讨论了两种使用 C++ 计算平均值超过给定数组中位数的 K 长度子数组的方法。第一种方法是强力方法,它迭代所有可能的 K 长度子数组并计算它们的平均值。第二种方法是一种优化方法,它使用前缀和数组来更有效地计算平均值。两个代码都已提供,可以执行以查找所需的子数组数量。










