【C++入門】配列内で唯一異なる要素を検索するアルゴリズムと実装例

本記事では、サイズnの整数型配列arr[]が与えられたとき、その中に一つだけ存在する「異なる要素」を見つける問題を、C++で解く方法を解説します。

配列には2種類の値しか含まれておらず、ひとつを除いたすべての要素が同一の値を持っています。その「仲間はずれ」の要素を効率よく特定することが目標です。

問題例

具体的な入出力の例を見てみましょう。

入力:

arr[] = {1, 1, 1, 2, 1, 1, 1, 1}

出力:

2

この例では、ほとんどの要素が「1」であるのに対し、「2」だけが異なるため、答えは2となります。

解法アプローチ

1. 全探索による単純なアプローチ(O(N²))

最も直感的な方法は、各要素について他のすべての要素と比較し、一致しないものを見つけることです。ただし、この方法では二重ループが必要となるため、時間計算量はO(N²)になり、要素数が多い場合には非効率です。

2. ハッシュテーブルを活用するアプローチ(O(N))

より効率的な方法として、ハッシュテーブル(連想配列)を使って各要素の出現回数を記録し、出現回数が1回だけの要素を出力する方法があります。時間計算量はO(N)に抑えられますが、その分メモリを消費します。

3. 隣接要素の比較による実装

さらに、先頭の数要素をチェックしたうえで隣接する要素同士を比較していくことで、追加のメモリを使わずにO(N)で解くことも可能です。以下がその実装例です。

C++での実装例

以下のプログラムは、配列内の異なる要素を検索して表示します。

#include <iostream>
using namespace std;

int findDiffElementArray(int arr[], int n){
    if (n == 1)
        return -1;
    if (n == 2)
        return arr[0];
    if (arr[0] == arr[1] && arr[0] != arr[2])
        return arr[2];
    if (arr[0] == arr[2] && arr[0] != arr[1])
        return arr[1];
    if (arr[1] == arr[2] && arr[0] != arr[1])
        return arr[0];
    for (int i = 3; i < n; i++)
        if (arr[i] != arr[i - 1])
            return arr[i];
    return -1;
}

int main(){
    int arr[] = { 5, 5, 1, 5, 5, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The different element in the array is "<<findDiffElementArray(arr, n);
    return 0;
}

コードの解説

このプログラムの処理の流れは以下のとおりです。

• 要素数が1の場合は「異なる要素」が存在しないため、-1を返します。
• まず最初の3つの要素を組み合わせて比較し、どれが異なる値なのかを判定します。
• 最初の3要素がすべて同じ値だった場合は、4番目以降の要素を直前の要素と順に比較し、異なる値が見つかった時点でそれを結果として返します。

実行結果

The different element in the array is 1

サンプル配列 {5, 5, 1, 5, 5, 5, 5} の場合、ほとんどの要素が「5」であり、「1」だけが異なるため、正しく「1」が出力されています。

まとめ

配列内で唯一異なる要素を検索する問題は、単純な全探索ではO(N²)の計算量がかかりますが、工夫次第でO(N)まで高速化できます。ハッシュテーブルを利用する方法や隣接要素を比較する方法など、データの性質や制約に応じて最適なアプローチを選択しましょう。