C++で配列内に偶数回出現する最初の要素を見つけるプログラム

この問題では、N個の整数値からなる配列 arr[] が与えられます。私たちのタスクは、配列内で偶数回出現する最初の要素を見つけるプログラムを作成することです。条件を満たす要素が存在する場合はその要素を返し、存在しない場合は false を表す -1 を返します。

問題を理解するための例

入力: arr[] = {2, 3, 7, 2, 3, 6, 4, 1, 2}
出力: 3

この例では、要素「2」は3回、「3」は2回出現しています。したがって、偶数回（2回）出現する最初の要素は「3」となり、これが出力となります。

解決アプローチ

この問題を解く最もシンプルな方法は、配列の各要素を1つずつ取り上げて、その要素の出現回数が偶数であるかどうかを確認し、偶数回出現する最初の要素を返すことです。しかし、この方法では時間計算量が O(N²) となり、大きな配列に対しては非効率です。

より効率的な解決策として、ハッシュマップ データ構造を使用する方法があります。この手法では、配列を走査しながらハッシュマップを作成し、各要素とその出現回数が偶数かどうかを表すトグル値（true / false）を格納します。こうすることで、出現回数そのものを毎回計算して偶奇を判定するオーバーヘッドを削減でき、トグル値を見るだけで必要な結果がわかるようになります。

アルゴリズムの手順

配列を走査し、各要素 arr[i] についてハッシュマップを以下のように操作します。

1. 要素がマップに存在しない場合：トグル値 'false' とともにマップへ追加します。
2. 要素がマップに既に存在する場合：対応するトグル値を反転させます。つまり 'true' なら 'false' へ、'false' なら 'true' へ切り替えます。

配列全体の走査が完了したら、再び配列を先頭から確認し、対応するトグル値が 'true'（偶数回出現を意味する）になっている最初の要素を返します。該当する要素が見つからなければ -1 を返します。

このアルゴリズムの時間計算量は O(N)、空間計算量も O(N) であり、素朴な方法よりも大幅に高速です。

実装例

上記のソリューションの動作を示すC++プログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
int findFirstEvenFreqVal(int arr[], int n){
   unordered_map<int, bool> freqTogMap;
   for (int i = 0; i < n; i++){
      if (freqTogMap.find(arr[i]) == freqTogMap.end())
         freqTogMap.insert(pair <int,bool> (arr[i],false));
      else
      {
         bool val = freqTogMap.find(arr[i])->second;
         if (val == true)
            freqTogMap.find(arr[i])->second = false;
         else
            freqTogMap.find(arr[i])->second = true;
      }
   }
   int j = 0;
   for (j = 0; j < n; j++){
      if (freqTogMap.find(arr[j])->second == true)
         return arr[j];
   }
   return -1;
}
int main(){
   int arr[] = { 2, 4, 6, 8, 1, 6 };
   cout<<"配列内で偶数回出現する最初の要素は "  <<findFirstEvenFreqVal(arr, 6);
   return 0;
}

出力結果

配列内で偶数回出現する最初の要素は 6

この例では、配列 {2, 4, 6, 8, 1, 6} の中で「6」だけが2回出現しているため、偶数回出現する最初の要素として「6」が出力されます。