数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的最大平均子数组 II
假设我们有一个包含 n 个整数的数组，我们需要找到长度大于或等于 k 的连续子数组，该子数组具有最大平均值。我们需要找到最大平均值。
因此，如果输入类似于 [1, 12, -5, -6, 50, 3]，k = 4，则输出将为 12.75，因为当长度为 5 时，最大平均值为 10.8，当长度为 6 时，最大平均值为 9.16667。因此输出为 12.75。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 ok()，它将接收 x、一个数组 nums 和 k，
n := nums 的大小
定义一个大小为 n 的数组 arr。
对于初始化 i := 0，当 i < n 时，更新（增加 i），执行：
arr[i] := nums[i] - x
sum := 0，last := 0
对于初始化 i := 0，当 i < k 时，更新（增加 i），执行：
sum := sum + arr[i]
如果 sum >= 0，则：
返回 true
对于初始化 i := 0，j := k，当 j < n 时，更新（增加 i），（增加 j），执行：
last := last + arr[i]
sum := sum + arr[j]
如果 last < 0，则：
sum := sum - last
last := 0
如果 sum >= 0，则：
返回 true
返回 false
从主方法执行以下操作：
ret := 0，low := -inf，high := inf
当 high - low > 10^-5 时，执行
mid := low + (high - low) / 2
如果 ok(mid, nums, k) 为 true，则：
low := mid
ret := mid
否则
high := mid
返回 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
832 次浏览
