C++で行列の修正平均より大きい要素の個数を求める方法

修正平均とは

本記事では、行列の「修正平均」より大きい要素がいくつあるかをC++で求める方法を解説します。まず、修正平均の定義を確認しましょう。

修正平均は次の式で定義されます。

(行ごとの最小値の合計 + 列ごとの最大値の合計) ÷ (行数 + 列数)

具体的な例を見てみましょう。

1 2 3
4 5 6
7 8 9

この行列の場合、修正平均は以下のように計算できます。

mean = (sum(1 + 4 + 7) + sum(7 + 8 + 9)) / (3 + 3)

つまり、まず修正平均を求め、その後、平均値より大きい要素の個数を数えます。上記の例では、修正平均は6となり、6より大きい要素は7、8、9の3つです。したがって、答えは3になります。

アルゴリズム

• 行列を初期化します。

• 各行の最小値を求め、その合計を計算します。

• 各列の最大値を求め、その合計を計算します。

• 上記の式を使って修正平均を求めます。

• 修正平均より大きい要素の個数を数えます。

C++での実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
#define m 3
#define n 3
int getElementCountGreaterThanMean(int matrix[][n]) {
    int rowSum = 0;
    for (int i = 0; i < m; i++) {
        int min = matrix[i][0];
        for (int j = 1; j < n; j++) {
            if (matrix[i][j] < min){
                min = matrix[i][j];
            }
        }
        rowSum += min;
    }
    int colSum = 0;
    for (int i = 0; i < n; i++) {
        int max = matrix[0][i];
        for (int j = 1; j < m; j++) {
            if (max < matrix[j][i]) {
                max = matrix[j][i];
            }
        }
        colSum += max;
    }
    int mean = (rowSum + colSum) / (m + n);
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mean < matrix[i][j]) {
                count++;
            }
        }
    }
    return count;
}
int main() {
    int matrix[m][n] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    cout << getElementCountGreaterThanMean(matrix) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

3

このコードの計算量はO(m×n)であり、行列の全要素を数回走査するだけで済むため、非常に効率的です。行ごとの最小値探索、列ごとの最大値探索、そして最後のカウント処理のそれぞれで行列全体を一度ずつ確認していますが、いずれも線形時間で完了します。