C ++中的最大平均子数组II
假设我们有一个n个整数的数组，我们必须找到长度大于或等于k且具有最大平均值的连续子数组。我们必须找到最大平均值。
因此，如果输入类似于[1,12，-5，-6,50,3]，k = 4，则输出将为12.75，如length为5时，最大值为10.8，length为6时，最大平均值为9.16667。因此输出为12.75。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数
ok()，它将使用x，一个数组nums，k，n：= nums的大小
定义大小为n的数组arr。
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-
arr [i]：= nums [i]-x
sum：= 0，last：= 0
对于初始化i：= 0，当i <k时，更新（将i增加1），执行-
sum：= sum + arr [i]
如果总和> = 0，则-
返回真
对于初始化i：= 0，j：= k，当j <n时，更新（i增加1），（j增加1），-
返回真
sum：= sum-最后
最后：= 0
最后：=最后+ arr [i]
sum：= sum + arr [j]
如果last <0，则-
如果总和> = 0，则-
返回假
从主要方法中执行以下操作-
ret：= 0，低：= -inf，高：= inf
当高-低> 10 ^ -5时
高：=中
低：=中
ret：=中
中：=低+（高-低）/ 2
如果ok(mid,nums,k)为真，则-
除此以外
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>using namespace std;
class Solution {
public:
bool ok(double x, vector <int>& nums, int k){
int n = nums.size();
double arr[n];
for (int i = 0; i < n; i++) {
arr[i] = nums[i] - x;
}
double sum = 0;
double last = 0;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
if (sum >= 0)
return true;
for (int i = 0, j = k; j < n; i++, j++) {
last += arr[i];
sum += arr[j];
if (last < 0) {
sum -= last;
last = 0;
}
if (sum >= 0)
return true;
}
return false;
}
double findMaxAverage(vector<int>& nums, int k) {
double ret = 0;
double low = INT_MIN;
double high = INT_MAX;
while (high - low > 1e-5) {
double mid = low + (high - low) / 2;
if (ok(mid, nums, k)) {
low = mid;
ret = mid;
} else {
high = mid;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,12,-5,-6,50,3};
cout << (ob.findMaxAverage(v, 4));
}
输入项
{1,12,-5,-6,50,3},4输出结果
12.75000
以上是 C ++中的最大平均子数组II 的全部内容， 来源链接： utcz.com/z/331117.html
