描述
有一个不为空且仅包含正整数的数组，找出其中出现频率最高的前 K 个数，时间复杂度必须在 O(n log n) 以内。
输入
一行数据包括两部分，一个正整数数组（数字间 ',' 分隔）和一个正整数 K （1 ≤ K ≤ 数组长度），数组和 K 之间有一个空格。
输出
输出包含前 K 个出现频率最高的数（出现频率相同时，较小的数在前），用 ', ' 分隔，保证升序排列。
输入样例
1,1,1,2,2,3 2
输出样例
1,2
解析：需要记录出现的数字及其次数，所以想到用关联容器map。又因为题目需要输出前K个最高频率，所以还需要通过频率值对map中的关键字进行排序。这里想到了优先队列priority_queue。设置频率值的大小为优先队列中的优先级，在完成对数列的计数之后，将map中记录的数据插入到优先队列中，在队列中完成自动的比较排序，最后输出优先级最高的K个数据。
首先对优先队列要有一些了解。
优先队列（priority_queue）是一个容器适配器，stack，queue也都是容器适配器。优先队列在队列的基础上在内部添加了一个排序，本质上是一个堆。在优先队列中，新加入的元素会排在所有优先级比他低的元素之前（这里的“前”实际上指的是队尾），即优先级越高，离队尾越近。
优先队列可以通过pq.top()来访问队尾第一个元素；通过pg.pop()来删除第一个元素。
而优先队列判断优先级的比较函数与正常的思路是相反的，比如下面图中所用的就是less<int>比较方法，而实际效果是从大到小排列。
定义优先队列需要输入三个参数。
priority_queue<Type, Container, Functional>
其中Type 是数据类型，Container 是容器类型，Functional 是比较的方式。STL中默认使用"()"比较。而比较中又默认使用less（即“<”）的方式。比如数组的排序sort()在默认情况下是用less，a<b，则a排在b的前面，即a更靠近数组头部，那么该数组为小根堆。在优先队列中使用默认less的方式，a<b，则a排在b的前面，即a更靠近队列队首，然而队列输出在队尾，所以此时该队列为大根堆。
若在一些需要自定义写比较方法的时候，则最好写比较结构体重载运算符"()"。
下面是本题的代码，用了关联容器加上大根堆优先队列，重载了运算符用来比较两个pair<int,int>。
#include <bits/stdc++.h>
using namespace std;
//用结构体重载运算符(),less方法，大根堆
struct cmp
{
bool operator()(const pair<int,int> &a ,const pair<int,int> &b)
{
if(a.second < b.second)
{
return true;
}
return false;
}
};
int main()
{
string input;
while(getline(cin,input))
{
//用map实现记录数字及其出现次数
map<int,int> mapping;
//res保存所要求的输出的前N个最高频率的数字
vector<int> res;
//用优先队列，设置优先级比较方式，在计数完之后插入
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
stringstream ss(input);
string item;
getline(ss,item,' ');
stringstream str(item);
getline(ss,item);
int num = stoi(item);
while(getline(str,item,','))
{
mapping[stoi(item)]++;
}
for(auto &c : mapping)
{
pq.push(make_pair(c.first , c.second));
}
for(int i = 0; i < num ; i++)
{
res.push_back(pq.top().first);
pq.pop();
}
for(int i = 0; i<res.size()-1; i++)
{
cout<<res[i]<<",";
}
cout<<res[res.size()-1]<<endl;
}
return 0;
}
