C++で正方行列の最大値と最小値を効率的に求める方法

問題文

n×n の正方行列が与えられたとき、その行列に含まれる要素の中から最大値と最小値を求めるプログラムを作成します。

例

例として、次のような 3×3 の行列が与えられたとします。

{{15, 17, 19}, {5, 1, 7}, {14, 5, 16}}

この場合、最小値は 1、最大値は 19 となります。

アルゴリズム

• 行列の各行について、行の先頭の要素と行の末尾の要素のように、対になる2つの要素を選びます。
• 選んだ2つの要素を比較し、小さい方を現在の最小値と、大きい方を現在の最大値と照らし合わせます。必要に応じて最小値・最大値を更新します。
• 2つの要素を処理するのに必要な比較は3回なので、行列全体を走査するのに必要な比較回数は合計で 3/2 × n² 回になります。これは全要素を1つずつ単純に比較する方法（2n² 回）と比べて効率的です。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
#define MAX 200
using namespace std;
void getMinMax(int matrix[MAX][MAX], int n) {
    int min = INT_MAX;
    int max = INT_MIN;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= n / 2; ++j) {
            if (matrix[i][j] > matrix[i][n - j - 1]) {
                if (min > matrix[i][n - j - 1]) {
                    min = matrix[i][n - j - 1];
                }
                if (max < matrix[i][j]) {
                    max = matrix[i][j];
                }
            } else {
                if (min > matrix[i][j]) {
                    min = matrix[i][j];
                }
                if (max < matrix[i][n - j - 1]) {
                    max = matrix[i][n - j - 1];
                }
            }
        }
    }
    cout << "Maximum = " << max << ", Minimum = " << min << endl;
}
int main() {
    int matrix[MAX][MAX] = { {15, 17, 19}, {5, 1, 7}, {14, 5, 16} };
    getMinMax(matrix, 3);
    return 0;
}

出力

Maximum = 19, Minimum = 1

まとめ

このアルゴリズムでは、行の両端から要素をペアで比較していくことで、比較回数を 3/2 × n² 回に抑えられます。行列のサイズが大きくなるほど、全要素を個別に比較する素朴な手法と比べて処理効率の向上が期待できます。