描述

有一个不为空且仅包含正整数的数组，找出其中出现频率最高的前 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>比较方法，而实际效果是从大到小排列。

优先队列示意图.png

定义优先队列需要输入三个参数。
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;
}