用C++编写一个程序，找出整数数组中出现频率最高的K个元素

Z时代
2024-01-10
分类：综合

假设我们有一个大小为 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}

输出-

说明- 在给定的整数数组中，在数组中频率最高的前 K=1 个元素是 {1}。

解决这个问题的方法

在给定的整数数组中，我们必须找到并返回那些在给定数组中大部分时间重复的数字。键 K 显示数组的顶部 K 元素，我们在遍历数组时必须返回该元素。

方法很简单。我们将创建一个哈希表，其中一个键作为当前元素，一个值作为该特定数字的出现。在对整个映射进行排序并找到每个元素的出现次数后，返回前 K 个最频繁元素的输出结果。

以 N 作为输入和 N 个元素的数组。
一个函数 topKfrequent(int *arr, int k) 以 arr[ ] 和键 K 作为输入并返回前 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;
}