C++で行列内のすべての要素が同一である行の数を数える方法

整数で構成される行列が与えられたとき、すべての要素が同一である行が何行あるかを求めるのが、この記事のテーマです。

例として、次のような 4×5 の行列を考えてみましょう。

この場合の答えは 2 です。1行目（すべてが 1）と3行目（すべてが 7）は、同一の要素のみで構成されているためです。

それでは、具体的な例で確認していきましょう。

入出力の例

例1

入力：

matrix =
    [ 1 1 1 1 ]
    [ 2 3 2 7 ]
    [ 3 3 3 3 ]

出力： 同一要素で構成される行の数 − 2

説明： 0行目はすべて 1、2行目はすべて 3 で構成されているため、該当する行は 2 行です。

例2

入力：

matrix =
    [ 1 2 3 4 ]
    [ 1 2 3 4 ]
    [ 1 2 3 4 ]

出力： 同一要素で構成される行の数 − 0

説明： どの行にも異なる要素が含まれているため、該当する行は 1 行もありません。

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

ここでは、行列を vector<vector<int>> として扱います。各行に対して set<int> を作成し、その行の要素をすべてセットに挿入していきます。set は重複する要素を持たないため、最終的にセットのサイズが 1 であれば、その行は同一の要素のみで構成されていると判断できます。

• 行列を vector<vector<int>> matrix として宣言し、初期化します。
• matrix.size() を使って行数を取得します。
• 関数 same_rows(vector<vector<int>> matrix, int size) は、行列とそのサイズを受け取り、同一要素で構成される行の数を返します。
• カウント用の変数を初期値 0 で用意します。
• for ループで i = 0 から i = size まで行列を走査します。
• 各行について、j = 0 から j < matrix[i].size() まで要素を走査します。
• 現在の行の要素を格納するための set<int> set_row を用意します。
• set_row.insert(matrix[i][j]) で、現在の行の要素をセットに追加していきます。
• 走査終了後、set_row のサイズを確認します。サイズが 1 であれば、その行は同一要素のみで構成されているため、カウントを増やします。
• すべての行の走査が終わったら、カウントを最終結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int same_rows(vector<vector<int>> matrix, int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        set<int> set_row;
        for (int j = 0; j < matrix[i].size(); j++){
            set_row.insert(matrix[i][j]);
        }
        if (set_row.size() == 1){
            count++;
        }
    }
    return count;
}

int main(){
    vector<vector<int>> matrix = {
        { 2, 2, 2, 2 },
        { 5, 5, 5, 5 },
        { 2, 2, 2, 2 },
        { 5, 5, 5, 5 }
    };
    int size = matrix.size();
    cout << "Count of rows in a matrix that consist of same element are: "
         << same_rows(matrix, size);
    return 0;
}

実行結果

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

Count of rows in a matrix that consist of same element are: 4

この例では、4 つの行すべてが同一の要素のみで構成されているため、結果は 4 となります。

計算量と補足

行数を N、列数を M とすると、このアルゴリズムの時間計算量は O(N × M)、空間計算量は各行ごとにセットを保持するため O(M) となります。

なお、追加メモリを使いたくない場合は、set を使わずに「各行の先頭要素とそれ以外の要素を順番に比較する」方法でも判定できます。この場合、空間計算量は O(1) に抑えられます。状況に応じて使い分けるとよいでしょう。