C++で各行がソートされた行列の全行に共通する要素を効率的に見つける方法

はじめに

各行が昇順にソートされた行列（2次元配列）が与えられたとします。このとき、すべての行に共通して存在する要素を見つける関数を作成する必要があります。

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

この行列の場合、すべての行に共通して現れる要素は 5 となります。

解決アプローチ：ハッシュテーブルを活用

この問題を解くには、ハッシュテーブル（連想配列）を利用したアプローチが有効です。この手法の大きな利点は、行がソートされていない場合でも同様に適用できるという点です。

アルゴリズムの手順

以下の手順に従って処理を進めます。

ステップ1： まず、1行目の各行の要素（重複を除く）をキーとしてハッシュテーブルを作成します。すべての値は 0 で初期化します。

ステップ2： 行列のすべての要素を走査します。ある要素がハッシュテーブルに存在する場合、そのカウントを 1 増やします。なお、同じ行内で同じ値が繰り返し出現してもカウントが重複して増えないよう、直前の要素と同じ値の場合はスキップします。

ステップ3： 最後に、カウントが行列の行数（M）と一致するキーが存在するかどうかを確認します。一致するキーがあれば、その要素はすべての行に存在することになります（1つの行内で同じ値が重複しないことを前提としています）。

C++での実装例

#include<iostream>
#include<unordered_map>
#define M 4
#define N 5
using namespace std;
int getCommonElement(int matrix[M][N]) {
    unordered_map<int, int> count;
    int i, j;
    for (i = 0; i < M; i++) {
        count[matrix[i][0]]++;
        for (j = 1; j < N; j++) {
            if (matrix[i][j] != matrix[i][j - 1])
            count[matrix[i][j]]++;
        }
    }
    for (auto ele : count) {
        if (ele.second == M)
        return ele.first;
    }
    return -1;
}
int main() {
    int matrix[M][N] = {
        { 1, 2, 3, 4, 5 },
        { 2, 4, 5, 8, 10 },
        { 3, 5, 7, 9, 11 },
        { 1, 3, 5, 7, 9 },
    };
    int result = getCommonElement(matrix);
    if (result == -1)
        cout << "No common element has found";
    else
        cout << "Common element is " << result;
}

実行結果

Common element is 5

コードのポイント

この実装では、unordered_map を使用して各要素の出現回数を記録しています。内側のループで matrix[i][j] != matrix[i][j - 1] という条件をチェックすることで、同じ行内での重複カウントを防止しています。これは、行がソートされている場合に特に有効なテクニックです。

計算量は、行列の全要素を一度走査するため O(M×N) となります。ここで M は行数、N は列数です。ハッシュテーブルへの挿入・検索は平均 O(1) で行えるため、全体として非常に効率的なアルゴリズムと言えます。

共通要素が存在しない場合は -1 を返すようになっており、呼び出し元でその判定を行うことで、共通要素の有無を柔軟に処理できます。