描述

有一个不为空且仅包含正整数的数组，找出其中出现频率最高的前 K 个数，时间复杂度必须在 O(n log n) 以内。

输入

一行数据包括两部分，一个正整数数组（数字间 ‘,’ 分隔）和一个正整数 K （1 ≤ K ≤ 数组长度），数组和 K 之间有一个空格。

输出

输出包含前 K 个出现频率最高的数（出现频率相同时，较小的数在前），用 ‘, ‘ 分隔，保证升序排列。

输入样例

1,1,1,2,2,3 2

输出样例

1,2

AC代码：

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

struct  key_value
{
    int num;
    int cnt;
};

int comp(const key_value &a,const key_value &b)
{
    if(a.cnt == b.cnt)
    {
        return a.num<b.num;
    }
    else
        return a.cnt>b.cnt;
}

int main()
{
    vector<int>a(0);
    int k ;
    int num;
    string s;
    while(cin>>s>>num)
    {
        s = s+",";
        bool flag = false;
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                a.push_back(b);
            }
        }
        sort(a.begin(),a.end());
        struct key_value book[a.size()+1];
        temp = a[0];
        j = 0;
        for(int i = 0; i<a.size(); i++)
        {
            if(temp == a[i])
            {
                cnt++;
            }
            else
            {
                book[j].num = temp;
                book[j].cnt = cnt;
                j++;
                temp = a[i];
                cnt = 1;
            }
        }
        book[j].num = temp;
        book[j].cnt = cnt;
        j++;
        sort(book,book+j,comp);
        if(num>0)
        {
            for(int i = 0; i<num-1; i++)
            {
                cout<<book[i].num<<",";
            }
            cout<<book[num-1].num<<endl;
        }
    }
}