C++で重複する2つの配列から欠落した要素を効率的に見つける方法

概要

互いにほぼ同じ内容を持つ2つの配列が与えられたとします。ただし、一方の配列にはもう一方に存在しない要素が1つだけ欠落しています。この記事では、その欠落している要素を特定するアルゴリズムをC++で解説します。

入力例1

arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}

出力例1

2

この場合、2番目の配列から「2」が欠落しています。

入力例2

arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}

出力例2

7

今度は、最初の配列から「7」が欠落しています。

アプローチ1：線形探索（シンプルな方法）

最も単純な解法は、両方の配列を先頭から順に走査し、要素を1つずつ比較していく方法です。不一致が見つかった時点で、その要素が欠落していると判断できます。

しかし、この方法の弱点は配列のサイズに比例した線形時間 O(n) が必要になる点です。データ量が多い場合は非効率になります。

アプローチ2：二分探索による効率的な解法

より効率的なのが二分探索（バイナリサーチ）を応用した手法です。以下の手順で処理を進めます。

• 大きい方の配列に対して二分探索を開始し、中間インデックス mid を (low + high) / 2 として求める。
• 両配列の mid 番目の値が一致していれば、欠落要素は右側の部分配列にあるため、low を mid に更新する。
• 一致していなければ、欠落要素は左側の部分配列にあるため、high を mid に更新する。
• low と high が隣接した時点でループを抜ける。
• 特別なケースとして、配列の要素数が0または1の場合や、先頭要素が既に異なる場合は、その要素自体が欠落要素となるため個別に処理する。

この方法により、計算量を O(log n) まで削減できます。なお、このアルゴリズムが正しく機能する前提として、両配列は同じ順序で並んでいる必要があります。

C++実装コード

// C++ program to find missing element from same
// arrays (except one missing element)
#include <bits/stdc++.h>
using namespace std;

// 二分探索を用いて欠落要素を特定する関数。
// arrA[] は大きい方の配列、Q はそのサイズ。
// arrA[] と arrB[] は同じ順序で並んでいるものとする。
int findMissingUtil(int arrA[], int arrB[], int Q){
    // 特別なケース：2番目の配列に1つだけ欠落がある場合
    if (Q == 1)
        return arrA[0];

    // 特別なケース：先頭要素がすでに異なる場合
    if (arrA[0] != arrB[0])
        return arrA[0];

    // 探索範囲の初期化
    int low = 0, high = Q - 1;

    // low < high の間ループ
    while (low < high){
        int mid = (low + high) / 2;

        // mid 番目の要素が一致していれば右側へ
        if (arrA[mid] == arrB[mid])
            low = mid;
        else
            high = mid;

        // low と high が隣接したら終了
        if (low == high - 1)
            break;
    }

    // 欠落要素は大きい方の配列の high 番目にある
    return arrA[high];
}

// 基本的なエラーチェックを行い findMissingUtil を呼び出す関数
void findMissing(int arrA[], int arrB[], int P, int Q){
    if (Q == P-1)
        cout << "Missing Element is "
            << findMissingUtil(arrA, arrB, P) << endl;
    else if (P == Q-1)
        cout << "Missing Element is "
            << findMissingUtil(arrB, arrA, Q) << endl;
    else
        cout << "Invalid Input";
}

// Driver Code
int main(){
    int arrA[] = {2, 5, 6, 8, 10};
    int arrB[] = {5, 6, 8, 10};
    int P = sizeof(arrA) / sizeof(int);
    int Q = sizeof(arrB) / sizeof(int);
    findMissing(arrA, arrB, P, Q);
    return 0;
}

実行結果

Missing Element is 2

まとめ

欠落要素の探索問題は、単純な線形探索でも解けますが、二分探索を活用することで O(log n) の高速な解法を実現できます。ポイントは「mid 番目の要素が一致するかどうか」で欠落位置が左か右かを判断できることにあります。ソート済み・同順序の配列が前提となるため、実務で使う際は入力条件の確認を忘れないようにしましょう。