資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
