C++で整数配列の中から最初に繰り返し現れる要素を検索する方法

問題の概要

この問題では、n個の整数値を含む配列arrが与えられます。私たちの課題は、整数配列の中から最初の繰り返し要素を見つけることです。

具体的には、配列内で2回以上出現している整数値のうち、最も早い位置(インデックス)に出現するものを特定する必要があります。

例で理解しましょう

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

説明 −

複数回出現している整数は「4」と「1」です。
4の最初の出現位置は1よりも前のため、答えは4となります。

解法アプローチ1:二重ループを使う単純な方法

最もシンプルな解決策は、ネストされたループ(二重ループ)を使用することです。外側のループで配列の各要素を順番に取り出し、内側のループで同じ値を持つ別の要素が配列内に存在するかどうかを確認します。同じ値が見つかった時点で、その値を結果として返します。

この方法は直感的で実装も容易ですが、解が存在しない場合や配列の後半にしか重複がない場合には、全要素の組み合わせを調べる必要があるため、計算量はO(N²)となり、大きな配列では非効率になります。

解法アプローチ2:ハッシュ(集合)を使う効率的な方法

より効率的に問題を解くには、ハッシュ(ここではset)を活用する方法があります。

ポイントは配列を末尾から先頭に向かって走査することです。走査しながら、すでに訪問した要素をsetに記録していきます。走査中に、すでに訪問済みの要素に再び遭遇した場合は、そのインデックスを「繰り返し要素の最小インデックス」として更新します。

末尾から走査することで、最後に更新されたインデックスが自動的に「繰り返し要素の中で最も左側にある要素」の位置となり、これが求める答えになります。この方法の計算量はO(N log N)(setを使用した場合)であり、二重ループよりも大幅に高速です。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include<bits/stdc++.h>
using namespace std;
int findRepeatingElementArray(int arr[], int n){
   int minRetIndex = -1;
   set<int> visitedElements;
   for (int i = n - 1; i >= 0; i--){
      if (visitedElements.find(arr[i]) != visitedElements.end())
         minRetIndex = i;
      else
         visitedElements.insert(arr[i]);
   }
   if (minRetIndex != -1)
      return arr[minRetIndex];
   else
      return -1;
}
int main(){
   int arr[] = {4, 1, 6, 3, 4, 1, 5, 8};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"繰り返し出現する要素は "<<findRepeatingElementArray(arr, n);
}

出力

繰り返し出現する要素は 4

まとめ

整数配列から最初の繰り返し要素を検索する問題では、二重ループによるO(N²)の単純な解法と、ハッシュセットを用いた効率的な解法があります。後者は配列を逆順に走査し、訪問済み要素を記録することで、最小のインデックスを持つ繰り返し要素を効率よく特定できます。データ量が多い場合やパフォーマンスが重要な場面では、ハッシュを活用したアプローチを選択するのがおすすめです。