用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个元素的数组。
一个函数topKfrequent(int*arr,intk)以arr[]和键K作为输入并返回前K个频繁元素。
创建所有元素及其出现的哈希图作为键和对。
对哈希图中的所有值进行排序。
bool辅助函数有助于按值对映射进行排序并按降序返回值。
迭代哈希图中的所有值并返回给定数组中前K个最频繁的元素。
示例
#includeusing namespace std; bool compare(pair &a, pair &b){ return a.second>b.second; } void topKfrequent(int arr,int n, int k){ unordered_map mp; for(int i=0;i >v(mp.begin(),mp.end()); sort(v.begin(),v.end(),compare); for(int i=0;i 输出结果 运行上面的代码将生成以下输出,
2 1在给定的整数数组中,前K=2个最频繁的元素是2,1。