【C++】NxM行列の各行に存在する配列要素の個数を数える方法

整数型の要素からなる配列と、行数・列数が指定された行列(2次元配列)が与えられ、配列の要素が行列の各行にいくつ存在するかを数えるのが本記事の課題です。

入力例と出力例

入力

int arr = { 2, 4, 6} と int matrix[row][col] = { { 2, 4, 6 }, {3, 4, 6}, {6, 2, 1}}

出力

第1行に存在する配列要素の数: 3
第2行に存在する配列要素の数: 2
第3行に存在する配列要素の数: 2

説明

配列には 2、4、6 の3つの要素が含まれています。配列の各要素と行列の要素を照合し、各行における出現数を数えます。1行目には 2、4、6 がすべて存在するため要素数は 3、2行目には 4 と 6 のみが存在するため 2、3行目には 2 と 6 のみが存在するため 2 となります。

入力

int arr = { 1, 3} と int matrix[row][col] = { { 1, 4, 6 }, {3, 1, 6}, {6, 2, 4}}

出力

第1行に存在する配列要素の数: 1
第2行に存在する配列要素の数: 2
第3行に存在する配列要素の数: 0

説明

配列には 1 と 3 の2つの要素が含まれています。1行目には 1 のみが存在するため要素数は 1、2行目には 1 と 3 の両方が存在するため 2、3行目にはどちらも存在しないため 0 となります。

プログラムで使用するアプローチ

この問題を解くには、素朴なアプローチ(ナイーブ法)と効率的なアプローチの複数の方法があります。まずは素朴なアプローチから見ていきましょう。

素朴なアプローチの手順

• 整数型の配列と、行数・列数を指定した行列を入力する

• 配列のサイズを計算し、配列・行列・配列のサイズを関数に渡して処理を続行する

• 行列の行に存在する要素の数を格納するための一時変数 count を用意する

• 0 から行列の行数まで FOR ループを開始する

• ループ内で、0 から配列のサイズまで FOR ループを開始する

• temp に arr[k] を代入する

• さらに 0 から行列の列数まで別の FOR ループを開始する

• ループ内で、temp == matrix[i][j] であるかを IF 文で判定し、一致していれば count を 1 増やす

• 行が切り替わるたびに count を 0 にリセットする

• 行が切り替わる前に count の値を出力する

効率的なアプローチの手順

• 整数型の配列と、行数・列数を指定した行列を入力する

• 配列のサイズを計算し、配列・行列・配列のサイズを関数に渡して処理を続行する

• 0 から行列の行数まで FOR ループを開始する

• unordered_map 型の変数を作成する

• さらに 0 から行列の列数まで別の FOR ループを開始する

• unordered_map に matrix[i][j] をキーとして値 1 を設定する

• 行列の行に存在する要素の数を格納するための一時変数 count を用意する

• ループ内で、0 から配列のサイズまで FOR ループを開始する

• um[arr[j]] == 1 であるかを IF 文で判定し、一致していれば count を 1 増やす

• 行が切り替わる前に count の値を出力する

実装例(素朴なアプローチ)

#include<bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
void arr_matrix(int matrix[row][col], int arr[], int size){
    int count = 0;
    //行列の行を走査
    for(int i=0; i<row; i++){
       //配列を走査
       for(int k=0 ; k<size ; k++){
           int temp = arr[k];
           //行列の列を走査
           for(int j = 0; j<col; j++){
               if(temp == matrix[i][j]){
                  count++;
               }
           }
       }
       cout<<"第"<< i + 1 <<"行に存在する配列要素の数: " << count << endl;
       count = 0;
    }
}
int main(){
    int matrix[row][col] = { { 2, 4, 6 }, {3, 4, 6}, {6, 2, 1}};
    int arr[] = { 2, 4, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    arr_matrix(matrix, arr, size);
}

出力

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

第1行に存在する配列要素の数: 3
第2行に存在する配列要素の数: 2
第3行に存在する配列要素の数: 2

実装例(効率的なアプローチ)

#include <bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
void arr_matrix(int matrix[row][col], int arr[], int size){
    for (int i = 0; i < row; i++){
        unordered_map<int, int> um;
        for (int j = 0; j < col; j++){
            um[matrix[i][j]] = 1;
        }
        int count = 0;
        for (int j = 0; j < size; j++) {
            if (um[arr[j]])
                count++;
        }
        cout<<"第"<< i + 1 <<"行に存在する配列要素の数: " << count << endl;
    }
}
int main(){
    int matrix[row][col] = { { 2, 4, 6 }, {3, 4, 6}, {6, 2, 1}};
    int arr[] = { 2, 4, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    arr_matrix(matrix, arr, size);
}

出力

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

第1行に存在する配列要素の数: 3
第2行に存在する配列要素の数: 2
第3行に存在する配列要素の数: 2

計算量の比較

素朴なアプローチでは、行・配列・列の三重ループを使用するため、時間計算量は O(row × col × size) となります。一方、効率的なアプローチでは unordered_map を使って各行の要素をハッシュテーブルに登録することで、配列要素の存在確認を O(1) で行えるため、時間計算量は O(row × (col + size)) に改善されます。データ量が大きい場合には、効率的なアプローチの採用を検討するとよいでしょう。