C++を使用してb回出現する唯一の要素を検索します

この問題では、サイズnのarr[]と2つの整数aとbが与えられます。私たちの仕事はf b回出現する唯一の要素を見つける 。

配列内でb回発生する1つの値を除いて、配列のすべての値は1回発生し、その値を見つける必要があります。

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

入力

arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1,1,1} a = 4, b = 3

出力

5

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

この問題の簡単な解決策は、各要素の出現をカウントし、それを2Dマトリックスに格納することです。次に、行列をトラバースして、発生頻度bの値を見つけます。

このアプローチの時間計算量はO（N ² です。 ）しかし、問題を解決できるより効果的なアプローチは、配列のすべての一意の要素の合計を見つけて、それをaで乗算することです。次に、この値から配列全体の合計を減算し、結果を（a-b）で除算します。結果の値は、発生頻度がbの値です。

例

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

#include <bits/stdc++.h>
using namespace std;
int findbFreqVal(int arr[], int n, int a, int b){
   unordered_set<int> uniqueVal;
   int uniqueValSum = 0, arrSum = 0;
   for (int i = 0; i < n; i++) {
      if (uniqueVal.find(arr[i]) == uniqueVal.end()) {
         uniqueVal.insert(arr[i]);
         uniqueValSum += arr[i];
      }
      arrSum += arr[i];
   }
   uniqueValSum = a * uniqueValSum;
   return ((uniqueValSum - arrSum) / (a - b));
}
int main(){
   int arr[] = { 4, 4, 4, 31, 8, 8, 8, 5, 5, 5};
   int a = 3, b = 1;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The value of the array that appears b times is "<<findbFreqVal(arr, n, a, b);
   return 0;
}

出力

The value of the array that appears b times is 31