题目：
https://pintia.cn/problem-sets/994805342720868352/problems/994805348471259136
测试用例3，4超时。借鉴学习了别人的代码（偷瞄一眼），发现我每次增加次数的时候，都要遍历，所以我改进成时间复杂度为O(1)的办法，即不用结构体记录次数，用散列表记录次数。改完后发现，我去，还是超时，真是坑的爆炸。现在的时间，主要浪费在排序上，我又仔细研读了别人的代码（仔细研读），发现，我去，大佬真是强的爆炸。排序可以剪枝，每次只排K+1位，有人会说，如果大家次数都是一样的，然后最后一个位置的次数加1，你k+1位排序能干嘛，还不是排不到。这就是大佬牛逼的地方，如果每次输出数组rec中只保留k位，即要输出的k位，每次都把新添加的进去排序，此时有k+1位，然后把最后一位剪了，又剩k位。下一次增加的，又和剩的k个排序。真的是佩服！！！
这样就是算法问题，不纠结在用set自带的排序还是sort排序。
//第一次写
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50010;
int n, k, num = 0;
struct Node{
int id;
int times;
}rec[maxn];
bool vis[maxn] = {false};
bool cmp(const Node &a, const Node &b){
if(a.times != b.times)
return a.times > b.times;
else
return a.id < b.id;
}
void update(int x){
if(vis[x]){
for(int i = 0; i < num; i++){
if(rec[i].id == x){
rec[i].times++;
return;
}
}
}
rec[num].id = x;
rec[num].times = 1;
num++;
vis[x] = true;
return;
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++){
int item;
scanf("%d", &item);
if(!i){
update(item);
sort(rec, rec+num, cmp);
continue;
}
printf("%d:", item);
for(int j = 0; j < k; j++){
if(j == num)
break;
printf(" %d", rec[j].id);
}
printf("\n");
update(item);
sort(rec, rec+num, cmp);
}
return 0;
}
//把结构体去除了
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50010;
int n, k, num = 0;
int rec[maxn];
int times[maxn] = {false};
bool cmp(const int &a, const int &b){
if(times[a] != times[b])
return times[a] > times[b];
else
return a < b;
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++){
int item;
scanf("%d", &item);
if(!i){
rec[num++] = item;
times[item] = 1;
continue;
}
printf("%d:", item);
for(int j = 0; j < k; j++){
if(j == num)
break;
printf(" %d", rec[j]);
}
printf("\n");
if(!times[item]){
rec[num++] = item;
times[item] = 1;
}
else
times[item]++;
sort(rec, rec+num, cmp);
}
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 50010;
int n, k, num = 0; //num记录rec里的数据数量
int rec[maxn];
int times[maxn] = {0};
bool hashtable[maxn] = {false}; //标记item在不在rec里
bool cmp(const int &a, const int &b){
if(times[a] != times[b])
return times[a] > times[b];
else
return a < b;
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++){
int item;
scanf("%d", &item);
if(!i){
rec[num++] = item;
times[item] = 1;
hashtable[item] = true;
continue;
}
printf("%d:", item);
for(int j = 0; j < k; j++){
if(j == num)
break;
printf(" %d", rec[j]);
}
printf("\n");
if(!times[item])
times[item] = 1;
else
times[item]++;
if(!hashtable[item]){
rec[num++] = item;
hashtable[item] = true;
}
sort(rec, rec+num, cmp);
if(num == k + 1){
hashtable[rec[--num]] = false;
rec[num] = 0;
}
}
return 0;
}
版权声明：本文为qq_38337299原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。