หาค่าเฉลี่ยของค่าเฉลี่ยซับอาร์เรย์ในอาร์เรย์ที่กำหนดใน C++

คำอธิบายปัญหา

ได้รับอาร์เรย์ arr[] ขนาด n และจำนวนเต็ม m ต้องการหา ค่าเฉลี่ยของค่าเฉลี่ย (Mean of Means) ของซับอาร์เรย์ทุกชุดที่มีขนาด m

ตัวอย่าง

Input: arr[] = {2, 5, 3, 6, 1}, m = 3

Output: 3.78

คำอธิบาย: ซับอาร์เรย์ขนาด 3 มี 3 ชุด:

• {2, 5, 3} → mean = 10/3
• {5, 3, 6} → mean = 14/3
• {3, 6, 1} → mean = 10/3

แนวทางแก้ปัญหา

วิธีที่ 1: Brute Force

หาซับอาร์เรย์ทุกชุดขนาด m → หาค่าเฉลี่ยแต่ละชุด → รวมค่าเฉลี่ยทั้งหมด → หารด้วยจำนวนชุด

วิธีที่ 2: Sliding Window (มีประสิทธิภาพกว่า)

1. คำนวณผลรวมของ Window แรก (index 0 ถึง m-1)
2. หาค่าเฉลี่ย Window แรก → บวกเข้า meanSum
3. Slide Window: ลบสมาชิกเก่าออก (arr[i-m]) บวกสมาชิกใหม่เข้า (arr[i])
4. คำนวณค่าเฉลี่ย Window ใหม่ → บวกเข้า meanSum
5. ทำซ้ำจนครบทุก Window
6. คืนค่า meanSum / windowCount โดย windowCount = n - m + 1

โค้ดตัวอย่าง C++

#include <iostream>
using namespace std;

float calcMeanOfSubarrayMeans(int arr[], int n, int m) {
    float meanSum = 0, windowSum = 0;
    
    // Window แรก
    for (int i = 0; i < m; i++)
        windowSum += arr[i];
    meanSum += (windowSum / m);
    
    // Slide window
    for (int i = m; 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