C++를 사용하여 b번 나타나는 유일한 요소 찾기

이 문제에서는 크기가 n인 arr[]과 두 개의 정수와 b가 주어집니다. 우리의 임무는 f b번 나타나는 유일한 요소에서 .

배열의 모든 값은 배열에서 b번 발생하는 하나의 값을 제외하고 한 번 발생하며 해당 값을 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

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