C++で3つのソート済み配列から共通要素を効率的に見つける方法

はじめに

3つの配列が与えられ、そのすべてに共通して存在する要素を見つけたいとします。例えば、配列が [10, 12, 15, 20, 25]、[10, 12, 13, 15]、[10, 12, 15, 24, 25, 26] の場合、3つの配列すべてに共通する要素は 10、12、15 となります。

配列がソート済みであることを利用すると、3つのポインタを使って各配列を一度だけ走査するだけで済む、非常に効率的なアルゴリズムが実現できます。時間計算量は O(n1 + n2 + n3) です。

アルゴリズムの考え方

配列 A1、A2、A3 を走査中の現在の要素をそれぞれ x、y、z とします。このとき、以下のケースが考えられます。

• x、y、z がすべて等しい場合：その値を共通要素として出力し、3つの配列のインデックスをそれぞれ1つ進めます。

• x < y の場合：x は共通要素になり得ないため、A1 のインデックスを進めます。

• x > z かつ y > z の場合：z は共通要素になり得ないため、A3 のインデックスを進めます。

サンプルコード

#include<iostream>
using namespace std;
void findCommonValues(int A1[], int A2[], int A3[], int n1, int n2, int n3) {
    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2 && k < n3) {
        if (A1[i] == A2[j] && A2[j] == A3[k]) {
            cout << A1[i] << " "; i++; j++; k++;
        }
        else if (A1[i] < A2[j])
            i++;
        else if (A2[j] < A3[k])
            j++;
        else
            k++;
    }
}
int main() {
    int A1[] = {10, 12, 15, 20, 25};
    int n1 = sizeof(A1)/sizeof(A1[0]);
    int A2[] = {10, 12, 13, 15};
    int n2 = sizeof(A2)/sizeof(A2[0]);
    int A3[] = {10, 12, 15, 24, 25, 26};
    int n3 = sizeof(A3)/sizeof(A3[0]);
    cout << "Common elements are: ";
    findCommonValues(A1, A2, A3, n1, n2, n3);
}

実行結果

Common elements are: 10 12 15

まとめ

この手法は、ソート済み配列の性質を活かし、3つのポインタを適切に進めることで共通要素を線形時間で検出できます。ハッシュセットを使う方法と比べて追加メモリが不要で、大規模なデータセットにも適したアプローチです。