크기가 N이고 키가 K인 정수 배열이 있다고 가정합니다. 우리의 임무는 배열에서 가장 자주 나타나는 K 상위 요소를 인쇄하는 것입니다. 예를 들어,
입력-1 -
N = 6
K = 2
arr[ ] = {1 ,1, 1, 2, 2, 3} 출력 -
1 2
설명 − 주어진 정수 배열에서 배열에서 가장 빈도가 높은 상위 K=2 요소는 {1,2}입니다.
입력-2 -
N = 2
K = 1
arr[ ] = {1, 2} 출력 -
1
설명 − 주어진 정수 배열에서 배열에서 가장 빈도가 높은 상위 K=1 요소는 {1}입니다.
이 문제를 해결하기 위한 접근 방식
주어진 정수 배열에서 우리는 주어진 배열에서 대부분 반복되는 숫자를 찾아서 반환해야 합니다. 키 K는 배열을 순회하는 동안 반환해야 하는 배열의 상위 K 요소를 보여줍니다.
접근 방식은 매우 간단합니다. 현재 요소로 키를 사용하고 특정 숫자의 발생으로 값을 사용하여 해시 테이블을 생성합니다. 전체 맵을 정렬하고 각 요소의 발생을 찾은 후 처음 K개의 가장 빈번한 요소의 출력 결과를 반환합니다.
-
N을 입력으로 사용하고 N 요소의 배열을 사용합니다.
-
arr[ ] 및 키 K를 입력으로 사용하고 상위 K개의 빈번한 요소를 반환하는 함수 topKfrequent(int *arr, int k).
-
모든 요소와 해당 발생의 해시맵을 키와 쌍으로 만듭니다.
-
해시맵의 모든 값을 정렬합니다.
-
bool 도우미 함수는 값을 기준으로 지도를 정렬하고 값을 내림차순으로 반환하는 데 도움이 됩니다.
-
해시맵의 모든 값을 반복하고 주어진 배열에서 가장 자주 사용되는 K 상위 요소를 반환합니다.
예
#include<bits/stdc++.h>
using namespace std;
bool compare(pair<int,int>&a, pair<int,int>&b){
return a.second>b.second;
}
void topKfrequent(int arr,int n, int k){
unordered_map<int,int>mp;
for(int i=0;i<n;i++){
mp[nums[i]]++;
}
vector<pair<int,int>>v(mp.begin(),mp.end());
sort(v.begin(),v.end(),compare);
for(int i=0;i<k;i++){
cout<<v[i].first<< " ";
}
}
int main(){
int N= 5;
int arr[N]= {1,1,3,2,2};
int k=2;
topKfrequent(arr,k);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
2 1
주어진 정수 배열에서 상위 K=2 가장 빈번한 요소는 2, 1입니다.