博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~
http://www.cnblogs.com/chenxiwenruo/p/6789819.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~
题意：用户每次选择一个indice，输出之前出现的频率最高的k个indice
如果恰好有两个频率一样，输出indice较小的那个
显然不能每次都要对当前所有的item排个序，会超时的
由于每次只要给出前k个出现频率最高的，如果出现频率一样，则给出值最小的
所以只要能存储前k个item的出现频率和值就行
用户每查询一个indice，先对当前的recommend进行排序，输出k个，不足k个的有多少输出多少，然后进行更新操作。
如果indice在当前的recommend里，那么只要更新下频率即可
如果不在的话，那么就要分情况了
如果当前recommend不足k个，那么往后添加一个新的即可
如果当前recomend已经有k个，只要将新的indice与最后一个进行比较与替换即可
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=+;
int cnt[maxn];
int n,k; struct Node{
int indice;
int cnt;
bool operator<(const Node tmp)const{
if(cnt==tmp.cnt){
return indice<tmp.indice;
}
else{
return cnt>tmp.cnt;
}
}
}recommend[+];
int main()
{
int indice;
int len;
Node node;
memset(cnt,,sizeof(cnt));
scanf("%d %d",&n,&k);
if(n>=){
scanf("%d",&indice);
cnt[indice]++;
node.cnt=cnt[indice];
node.indice=indice;
recommend[]=node;
len=;
}
for(int i=;i<n;i++){
scanf("%d",&indice);
printf("%d:",indice);
//当len<k的时候，若没在len个里面出现过，往recommend数组后面添就行
if(len<k){
sort(recommend,recommend+len);
bool isExist=false;
int idx;
for(int j=;j<len;j++){
printf(" %d",recommend[j].indice);
if(recommend[j].indice==indice){
isExist=true;
recommend[j].cnt++;
cnt[indice]++;
}
}
if(!isExist){
recommend[len].indice=indice;
recommend[len].cnt=cnt[indice]=;
len++;
}
}
//如果recommend已经有k个了，那么如果在这k个里面没出现过，当前的就得和第k个比较了
else{
sort(recommend,recommend+k);
bool isExist=false;
int idx;
for(int j=;j<k;j++){
printf(" %d",recommend[j].indice);
if(recommend[j].indice==indice){
isExist=true;
recommend[j].cnt++;
cnt[indice]++;
}
}
if(!isExist){
cnt[indice]++;
if(cnt[indice]>recommend[k-].cnt ||(cnt[indice]==recommend[k-].cnt && indice<recommend[k-].indice)){
recommend[k-].cnt=cnt[indice];
recommend[k-].indice=indice;
}
}
}
printf("\n");
}
return ;
}