整数の配列C++で最初の繰り返し要素を検索します

この問題では、n個の整数値の配列arrです。私たちのタスクは、整数の配列の最初の繰り返し要素を見つけることです。 。

配列内で複数回発生した配列から最初の整数値を見つける必要があります。

問題を理解するために例を見てみましょう

Input : arr[] = {4, 1, 8, 9, 7, 2, 1, 6, 4}
Output : 4

説明 −

Integers with more than one occurrence are 4 and 1.
4's first occurrence is smaller than 1. Hence the answer is 4

ソリューションアプローチ

この問題の簡単な解決策は、ネストされたループを使用することです。 2つのループを使用します。外側のループは配列の各整数値を反復処理し、内側のループは同じ値の別の整数値が配列に存在するかどうかを確認します。はいの場合、値を返します。この方法は優れていますが、解決策がない場合は、O（N2）の複雑さがあります。

ソリューションアプローチ

問題をよりよく解決できる別のアプローチは、ハッシュを使用することです。最後のインデックスから配列をトラバースしてから、アクセスしたインデックスで見つかった要素の最小インデックスを更新します。

例

ソリューションの動作を説明するプログラム

#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<<"The element with repeated occurence is "<<findRepeatingElementArray(arr, n);
}

出力

The element with repeated occurence is 4