C++の配列に偶数回出現する最初の要素

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

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

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

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

この問題を解決する簡単な方法は、配列の各要素を1つずつ検討し、要素の出現頻度を均等にチェックして、配列の最初の要素を偶数の出現頻度で返すことです。この問題を解決する別の方法は、ハッシュマップを使用することです。 データ構造。このために、配列をトラバースし、要素をトグルとして出現頻度とともに格納するハッシュマップを作成します。つまり、偶数かどうかに基づいてtrueまたはfalseを作成します。これにより、トグルによって必要な結果が表示されるため、発生頻度がtrueかfalseかをチェックするオーバーヘッドが削減されます。マップの場合、値が真である（発生頻度が偶数であることを示す）最初の要素が必要な結果です。

配列をトラバースし、値ごとに、配列内、つまりarr[i]マップをチェックインします

マップに存在しない場合は、トグル値' falseを使用してマップに追加します。 '。マップに存在する場合は、それに対応する現在の値を切り替えます。つまり、' true 'それを'false '、および' false 'それを'true '。

配列の反復後、マップを反復し、最初の値と対応するトグルの値を' trueとして返します。 '。

例

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

#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<<"The first element of the array which appears even number of times is "  <<findFirstEvenFreqVal(arr, 6);
   return 0;
}

出力

The first element of the array which appears even number of times is 6