C++で行列のすべての行に共通する重複しない要素を効率的に検索する方法

概要

m × m の正方行列が与えられたとき、その行列のすべての行に共通して現れる重複しない要素をすべて求めるのがこの問題です。出力される要素の順序は問われません。

入力例

mat[][] = { {13, 2, 15, 4, 17},
{15, 3, 2, 4, 36},
{15, 2, 15, 4, 12},
{15, 26, 4, 3, 2},
{2, 19, 4, 22, 15}
}

出力例

2 4 15

この例では、5つの行すべてに「2」「4」「15」が含まれているため、これら3つの値が出力されます。

解法アプローチ

方法1: 三重ループによる総当たり

3つのネストしたループを使い、1行目の各要素がそれ以降のすべての行に存在するかどうかを確認する方法です。この場合、時間計算量は O(m³) となり、さらに重複要素の出力を防ぐために追加の記憶領域が必要になることがあります。単純ですが、大規模な行列では非効率です。

方法2: ソート + ポインタ走査(推奨)

まず行列の各行を個別に昇順にソートします。その後、「3つのソート済み配列から共通要素を求める」問題の考え方を拡張した手法を適用します。各行ごとに現在の走査位置(カラムインデックス)を保持し、1行目の候補値に対して他の行を先頭から順に進めていくことで、効率的に共通要素を特定できます。この方法は時間計算量 O(m²) で動作し、追加の補助配列も最小限で済みます。

C++ 実装例

// C++ implementation to find distinct elements
// common to all rows of a matrix
#include <bits/stdc++.h>
using namespace std;
const int MAX1 = 100;
// 各行を昇順にソートする関数
void sortRows1(int mat1[][MAX1], int m){
    for (int i=0; i<m; i++)
        sort(mat1[i], mat1[i] + m);
}
// 共通するすべての要素を見つけて表示する関数
void findAndPrintCommonElements1(int mat1[][MAX1], int m){
    // 各行を個別にソート
    sortRows1(mat1, m);
    // 各行の現在の列インデックスを格納
    // (その行で要素を探索する開始位置)
    int curr_index1[m];
    memset(curr_index1, 0, sizeof(curr_index1));
    int f = 0;
    for (; curr_index1[0]<m; curr_index1[0]++){
        // 1行目の現在の列インデックスにある値
        int value1 = mat1[0][curr_index1[0]];
        bool present1 = true;
        // 'value' を残りのすべての行から探索
        for (int i=1; i<m; i++){
            // 現在の列インデックスから行末まで、
            // 'value' 以上の要素が見つかるまで進む
            while (curr_index1[i] < m &&
                mat1[i][curr_index1[i]] <= value1)
                curr_index1[i]++;
            // 直前の位置に 'value' が存在しなければ共通ではない
            if (mat1[i][curr_index1[i]-1] != value1)
                present1 = false;
            // ある行の走査が完了した場合
            if (curr_index1[i] == m){
                f = 1;
                break;
            }
        }
        // 'value' がすべての行に共通していれば出力
        if (present1)
            cout << value1 << " ";
        // どれか1行でも走査し終えたら、
        // それ以上の共通要素は存在しない
        if (f == 1)
            break;
    }
}
// 動作確認用ドライバプログラム
int main(){
    int mat1[][MAX1] = { {13, 2, 15, 4, 17},{15, 3, 2, 4, 36},{15, 2, 15, 4, 12},
        {15, 26, 4, 3, 2},{2, 19, 4, 22, 15}};
    int m = 5;
    findAndPrintCommonElements1(mat1, m);
    return 0;
}

実行結果

2 4 15

処理のポイント

• 事前ソート: 各行をソートしておくことで、二分探索的な走査が可能になり、計算量が大幅に削減されます。
• インデックス管理: curr_index 配列により、各行の走査位置を独立して追跡できます。一度進めた位置は巻き戻さないため、全体で各要素は高々1回ずつ比較されます。
• 早期終了: いずれかの行の走査が末尾に達した時点で、それ以上共通要素は存在しないため、即座にループを抜けます。
• 重複排除: ソート後の走査では同じ値が連続しても1回だけ判定・出力されるため、結果には重複しない要素のみが含まれます。