陣列元素與前綴平均值比較：找出小於前綴平均值的元素

問題描述

給定一個長度為 n 的陣列，輸出所有滿足「該元素值小於其前面所有元素（含自身）平均值」的元素。

算法思路

1. 遍歷陣列，維護運行總和 sum 和計數 cnt。
2. 對於第 i 個元素 arr[i]，計算前綴平均值 avg = sum / cnt（含當前元素）。
3. 若 arr[i] < avg，則輸出該元素。
4. 更新 sum += arr[i]，cnt++。

代碼實現 (C++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector a = {5, 2, 8, 1, 9, 3};
    long long sum = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        sum += a[i];
        double avg = static_cast(sum) / (i + 1);
        if (a[i] < avg) {
            cout << a[i] << " ";
        }
    }
    return 0;
}

示例

輸入：{5, 2, 8, 1, 9, 3}
前綴平均值：5, 3.5, 5, 4, 5, 4.67
輸出：2 1 3

複雜度

時間 O(n)，空間 O(1)。