크기가 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의 빈도를 갖습니다.