使用 C++ 查找唯一出现 b 次的元素

在这个问题中，我们得到一个大小为 n 的 arr[] 和两个整数 a 和 b。我们的任务是找出唯一出现 b 次的元素。

数组的所有值都出现一次，除了一个在数组中出现 b 次的值，我们需要找到该值。

让我们举个例子来理解这个问题，

输入

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

输出

5

解决方法

该问题的一个简单解决方案是计算每个元素的出现次数，然后将其存储在二维矩阵中。然后遍历矩阵找到出现频率为b的值。

这种方法的时间复杂度为 O(N ² )，但可以解决该问题的更有效方法是找到数组中所有唯一元素的总和，然后将其乘以 a。然后从该值中减去整个数组的总和，然后将结果除以 (ab)。结果值是出现频率为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<<"出现 b 次的数组的值为 "<<findbFreqVal(arr, n, a, b);
   return 0;
}

出现 b 次的数组的值为 31