根据id排序 排序复杂度O(logn) 查询O(n) 空间复杂度O(1) 除去存数据的数组
C++
#include<iostream>
#include<algorithm>
#define id first
#define time second
using namespace std;
const int N=100010;
typedef pair<int, int> PII;
PII logs[N];
int main() {
int n,d,k;
cin>>n>>d>>k;
for(int i=1;i<=n;i++)cin >> logs[i].time >> logs[i].id;//id为第一个 时间为第二个 方便以id排序
sort(logs+1,logs+n+1);//优先id在一起 然后在根据时间排序
int l=1,r=k;//维护一个长度为k的滑动窗口 表示有k个点赞
while (r<=n){
if(logs[l].id==logs[r].id){//该id还有k个点赞
if(logs[r].time-logs[l].time<d){//这k个赞最后一次点赞时间与第一次点赞时间差值 在d之间内
cout<<logs[l].id<<endl;//输出答案
while (r<=n&&logs[r].id==logs[l].id)r++;//找到下一个帖子
l=r;//直接维护下一个滑块
r+=k-1;
}else{//时间超过了 滑块向后移动
l++;
r++;
}
}else{//凑不齐k个赞
while (r<=n&&logs[r].id==logs[l].id)r++;//找到下一个帖子
l=r;//直接维护下一个滑块
r+=k-1;
}
}
return 0;
}
java
import java.util.Arrays;
import java.util.Scanner;
/**
* @作者 Brown
* @日期 2021/12/15 15:45
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), d = sc.nextInt(), k = sc.nextInt();
int[][] a = new int[n + 1][2];
for (int i = 1; i <= n; i++) {
a[i][0] = sc.nextInt();
a[i][1] = sc.nextInt();
}
//根据id号排序 id相同时间排序
Arrays.sort(a, 1, n+1, (o1, o2) -> o1[1] != o2[1] ? o1[1] - o2[1] : o1[0] - o2[0]);
int l = 1, r = k;
while (r <= n) {
if(a[l][1]==a[r][1]){
if(a[r][0]-a[l][0]<d){//满足d时间内
System.out.println(a[l][1]);
//找到下一个帖子
while (r<=n&&a[r][1]==a[l][1])r++;
l=r;
r+=k-1;
}else {
//不在规定时间内滑块向后移
r++;
l++;
}
}else { //凑不齐k个赞了 //找到下一个帖子
while (r<=n&&a[r][1]==a[l][1])r++;
l=r;
r+=k-1;
}
}
}
}