算法1

思路:双指针算法

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef pair<int,int> PII;

#define x first
#define y second

const int N=100010;

int n,d,k;

PII logs[N];//记录编号和id
int cnt[N];//用来记录每个id出现了几次
bool st[N];//记录每个帖子是否是热帖

int main(){

   scanf("%d%d%d",&n,&d,&k);//处理输入
   for(int i=0;i<n;i++)scanf("%d%d",&logs[i].x,&logs[i].y);

   sort(logs,logs+n);//先将编号从小到大排序

   for(int i=0,j=0;i<n;i++){

       int id=logs[i].y;//单独把id提取出来统计出现次数,也就是统计点赞数多少
       cnt[id]++;
       while(logs[i].x-logs[j].x>=d) {//这里是优化代码,在一个时间段内,重复出现的不需要再次统计,
       //所以logs[j]--

           cnt[logs[j].y]--;
           j++;

       }
       if(cnt[id]>=k)st[id]=true;//如果超过规定的个数,则认为是热频,保存到st数组

   }
    for(int i=0;i<=100000;i++){//输出数组
        if(st[i])
            printf("%d\n",i);
    }

    return 0;
}