n개의 정수가 있는 배열이 있다고 가정하고, 길이가 최대 평균값을 갖는 k보다 크거나 같은 연속적인 하위 배열을 찾아야 합니다. 최대 평균값을 찾아야 합니다.
따라서 입력이 [1,12,-5,-6,50,3], k =4와 같으면 출력은 길이가 5일 때 최대 평균값이 10.8, 길이가 6일 때와 같이 12.75가 됩니다. , 최대 평균값은 9.16667입니다. 따라서 출력은 12.75입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ok() 함수를 정의하면 x, 배열 nums, k,
가 필요합니다. -
n :=숫자 크기
-
n.
크기의 배열 arr을 정의합니다. -
initialize i :=0의 경우, i
-
arr[i] :=nums[i] - x
-
-
합계 :=0, 마지막 :=0
-
initialize i :=0의 경우, i
-
합계 :=합계 + arr[i]
-
-
합계>=0이면 -
-
true를 반환
-
-
초기화 i :=0, j :=k, j
-
마지막 :=마지막 + arr[i]
-
합계 :=합계 + arr[j]
-
마지막 <0이면 -
-
합계 :=합계 - 마지막
-
마지막 :=0
-
-
합계>=0이면 -
-
true를 반환
-
-
-
거짓을 반환
-
주요 방법에서 다음을 수행하십시오 -
-
ret :=0, 낮음 :=-inf, 높음 :=inf
-
높음 - 낮음> 10^-5 동안 수행
-
중간 :=낮음 + (높음 - 낮음) / 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