数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用C++查找只出现b次的元素
在这个问题中，我们得到一个大小为n的数组arr[]和两个整数a和b。我们的任务是找到只出现b次的元素。
数组的所有值都出现a次，只有一个值出现b次，我们需要找到那个值。
让我们来看一个例子来理解这个问题：
输入
arr[] = {3, 3, 3, 3, 5, 5, 5, 1, 1,1,1} a = 4, b = 3输出
5
解决方案
一个简单的解决方案是通过计算每个元素的出现次数，然后将其存储在二维矩阵中。然后遍历矩阵以查找出现频率为b的值。
这种方法的时间复杂度为O(N2)，但一个更有效的方法是找到数组所有唯一元素的和，然后乘以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
更新于：2022年2月11日
101 次浏览
广告