C ++でプログラムを作成して、整数の配列で上位K個の頻繁な要素を見つけます

サイズ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）。

• すべての要素とその出現箇所のハッシュマップをキーとペアとして作成します。

• ハッシュマップ内のすべての値を並べ替えます。

• ブールヘルパー関数は、マップを値で並べ替え、値を降順で返すのに役立ちます。

• ハッシュマップ内のすべての値を反復処理し、指定された配列内で最も頻度の高い上位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です。