C++로 프로그램을 작성하여 주어진 정수 배열에서 가장 빈번한 요소를 찾으십시오.

크기가 N인 정수 배열이 있다고 가정해 보겠습니다. 작업은 주어진 정수 배열에 존재하는 가장 빈번한 요소를 찾는 것입니다. 예를 들어,

입력-1 -

N = 8
A[ ] = {1,2,4,3,3,1,1,5}

출력 -

1

설명 − 주어진 정수 배열에서 가장 많이 나타나는 숫자는 '1'입니다. 따라서 출력은 '1'입니다.

입력-2 -

N = 6
A[ ] = {1,4,4,4,1,1}

출력-a -

1

출력-b -

4

설명:주어진 정수 배열에서 가장 많이 나타나는 숫자는 '1'과 '4'입니다. 따라서 출력을 그 중 하나로 반환할 수 있습니다.

이 문제를 해결하기 위한 접근 방식

주어진 배열에는 배열에 있는 가장 빈번한 요소를 찾아야 하는 여러 정수가 포함되어 있습니다. 선형 시간 O(n) 및 선형 공간 O(n)에서 이 문제를 해결하기 위해 해시맵 접근 방식을 사용할 수 있습니다.

이 접근 방식에서는 키가 요소가 되고 값이 요소의 발생이 되는 키-값 쌍으로 구성된 정렬되지 않은 맵(STL 라이브러리)을 만듭니다. 지도를 탐색하는 동안 숫자의 최대 발생을 찾고 숫자를 출력으로 반환합니다.

• N 크기의 배열을 입력하십시오.

• 정수 함수 maxOccurrence(int A[], int size)는 배열과 그 크기를 입력으로 받아 최대 빈도의 숫자를 반환합니다.

• 키를 요소로, 값을 빈도로 사용하여 배열의 모든 요소에 대한 해시맵을 생성합니다.

• 맵을 반복하고 가장 빈도가 높은 요소가 있는지 확인한 다음 결과를 숫자로 반환합니다. 그렇지 않고 배열에 숫자가 없으면 '-1'을 반환합니다.

예시

#include<bits/stdc++.h>
using namespace std;
int maxOccurrence(int A[], int size){
   int mxcount=0;
   int res=-1;
   unordered_map<int,int>mp;
   for(int i=0;i<size;i++){
      mp[A[i]]++;
   }
   for(auto x:mp){
      if(x.second>mxcount){
         res= x.first;
         mxcount=x.second;
      }
   }
   return res;
}
int main(){
   int N=6;
   int A[N]= {1,4,4,4,2,1};
   int ans= maxOccurrence(A,N);
   cout<<ans<<endl;
   return 0;
}

출력

위의 코드를 실행하면 출력이 다음과 같이 인쇄됩니다.

4

4는 주어진 배열에 있는 다른 모든 숫자의 최대 빈도인 3의 빈도를 갖습니다.