【C++】2次元配列から位置要素（行・列の最大値・最小値）の数を求める方法

この記事では、2次元配列 mat[n][m] が与えられたときに、「位置要素」の数を求める問題を解説します。

ここでいう「位置要素」とは、その要素が属する行または列における最大値もしくは最小値に該当する要素のことを指します。

入力例

mat[][] = {2, 5, 7}
{1, 3, 4}
{5, 1, 3}

出力例

8

説明

上記の行列では、2, 5, 7, 1, 4, 5, 1, 3 の8つの要素が位置要素に該当します。たとえば1行目の最大値は7、最小値は2であるため、どちらも位置要素としてカウントされます。

解法アプローチ

最もシンプルな解き方は、次の手順に従う方法です。

1. 各行の最大値・最小値をあらかじめ計算し、配列に保存する
2. 各列の最大値・最小値をあらかじめ計算し、配列に保存する
3. すべての要素を走査し、その要素が行または列の最大値・最小値のいずれかと一致するかを判定してカウントする

最大値・最小値を事前に求めておくことで、各要素の判定を定数時間で行えます。そのため、全体の時間計算量は O(m×n)、必要な追加メモリは O(m+n) に抑えられます。

C++での実装例

#include <iostream>
using namespace std;
const int MAX = 100;
int countAllPositionalElements(int mat[][MAX], int m, int n){
    int rowmax[m], rowmin[m];
    int colmax[n], colmin[n];
    for (int i = 0; i < m; i++) {
        int rminn = 10000;
        int rmaxx = -10000;
        for (int j = 0; j < n; j++) {
            if (mat[i][j] > rmaxx)
                rmaxx = mat[i][j];
            if (mat[i][j] < rminn)
                rminn = mat[i][j];
        }
        rowmax[i] = rmaxx;
        rowmin[i] = rminn;
    }
    for (int j = 0; j < n; j++) {
        int cminn = 10000;
        int cmaxx = -10000;
        for (int i = 0; i < m; i++) {
            if (mat[i][j] > cmaxx)
                cmaxx = mat[i][j];
            if (mat[i][j] < cminn)
                cminn = mat[i][j];
        }
        colmax[j] = cmaxx;
        colmin[j] = cminn;
    }
    int positionalCount = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if ((mat[i][j] == rowmax[i]) || (mat[i][j] == rowmin[i]) ||
                (mat[i][j] == colmax[j]) || (mat[i][j] == colmin[j])) {
                positionalCount++;
            }
        }
    }
    return positionalCount;
}
int main(){
    int mat[][MAX] = {
        { 2, 5, 7 },
        { 1, 3, 4 },
        { 5, 1, 3 }
    };
    int m = 3, n = 3;
    cout<<"Number of positional elements is "<<countAllPositionalElements(mat, m, n);
    return 0;
}

実行結果

Number of positional elements is 8

まとめ

本記事では、2次元配列から位置要素（行または列の最大値・最小値に該当する要素）の数を数える方法を紹介しました。ポイントは、行ごと・列ごとの最大値と最小値を事前に計算しておくことで、各要素の判定を高速に行える点です。計算量は O(m×n) と効率的であり、実用的なアルゴリズムとなっています。