สมมติว่าเรามีอาร์เรย์ที่มีจำนวนเต็ม n ตัว เราต้องหาอาร์เรย์ย่อยที่อยู่ติดกันซึ่งมีความยาวมากกว่าหรือเท่ากับ k ที่มีค่าเฉลี่ยสูงสุด เราต้องหาค่าเฉลี่ยสูงสุด
ดังนั้น หากอินพุตเป็น [1,12,-5,-6,50,3] k =4 เอาต์พุตจะเป็น 12.75 เช่นเมื่อความยาวเท่ากับ 5 ค่าเฉลี่ยสูงสุดคือ 10.8 เมื่อความยาวเท่ากับ 6 , ค่าเฉลี่ยสูงสุดคือ 9.16667 ดังนั้นเอาต์พุตคือ 12.75
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน ok() ซึ่งจะใช้ x, ตัวเลขอาร์เรย์, k,
-
n :=ขนาดของ nums
-
กำหนดขนาดอาร์เรย์ arr:n.
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
arr[i] :=nums[i] - x
-
-
ผลรวม :=0, สุดท้าย :=0
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน
-
sum :=sum + arr[i]
-
-
ถ้าผลรวม>=0 แล้ว −
-
คืนความจริง
-
-
สำหรับการเริ่มต้น i :=0, j :=k เมื่อ j
-
สุดท้าย :=สุดท้าย + arr[i]
-
sum :=sum + arr[j]
-
ถ้าสุดท้าย <0 แล้ว −
-
sum :=sum - สุดท้าย
-
สุดท้าย :=0
-
-
ถ้าผลรวม>=0 แล้ว −
-
คืนความจริง
-
-
-
คืนค่าเท็จ
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
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
