ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n และจำนวนเต็ม m หน้าที่ของเราคือค้นหาค่าเฉลี่ยของค่าเฉลี่ยของอาร์เรย์ย่อยในอาร์เรย์ที่กำหนด
คำอธิบายโค้ด − ในที่นี้ เราจำเป็นต้องหาค่าเฉลี่ยของอาร์เรย์เป็นค่าเฉลี่ยของอาร์เรย์ย่อยที่มีขนาด m
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {2, 5, 3, 6, 1}, m = 3 ผลลัพธ์
3.78
คำอธิบาย
All subarrays of size m are {2, 5, 3}, {5, 3, 6}, {3, 6, 1}
Means of means of subarray of size m, $$(\left(\frac{2+5+3}{3}\right)+\left(\frac{5+3+6}{3}\right)+\left(\frac{3+6 +1}{3}\right))/3=\left(\frac{10}{3}\right)+\left(\frac{14}{3}\right)+\left(\frac{10 }{3}\right)/3=34/3/3=3.78$$
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการค้นหาอาร์เรย์ย่อยทั้งหมดที่มีขนาด m และหาวิธีการ จากนั้นเพิ่มวิธีการทั้งหมดเหล่านี้แล้วหารด้วยจำนวนอาร์เรย์ย่อย และส่งคืนผลลัพธ์
วิธีที่มีประสิทธิภาพมากขึ้นอีกวิธีหนึ่งคือการใช้อัลกอริธึมหน้าต่างบานเลื่อน เราจะพบการค้นหาขนาด m โดยเริ่มจากดัชนี 0 สำหรับแต่ละหน้าต่าง ให้หาค่าเฉลี่ยและผลรวม และในตอนท้ายให้หารผลรวมตามจำนวนหน้าต่างแล้วคืนค่ากลับมา
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
float calcMeanOfSubarrayMeans(int arr[], int n, int m) {
float meanSum = 0, windowSum = 0;
for (int i = 0; i < m; i++)
windowSum += arr[i];
meanSum += (windowSum / m);
for (int i = 0; i < n; i++) {
windowSum = windowSum - arr[i - m] + arr[i];
meanSum += (windowSum / m);
}
int windowCount = n - m + 1;
return (meanSum / windowCount);
}
int main() {
int arr[] = { 4, 1, 7, 9, 2, 5, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int m = 3;
cout<<"The mean of subarray means is "<<calcMeanOfSubarrayMeans(arr, n, m);
return 0;
} ผลลัพธ์
The mean of subarray means is 8.06667
