这一个题，就这一个 猿猿太菜了，整整花费了一天半才把他搞明白，感觉内心受到了打击，被虐的真难受。一天半啥也没干，想思路想半天，代码实现半天，最后还没实现成功，分析别人代码小半天，最后抄别人代码一遍，才真正理解其中规律。
至于图解分析，猿猿累了，心情好了以后有空在来补充图解分析吧，暂时先贴上我的解决过程,都在代码注释中哦。
题目
日志统计
时间限制: 1.0s 内存限制: 512.0MB
【问题描述】
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是：
ts id
表示在ts时刻编号id的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
【输入格式】
第一行包含三个整数N、D和K。
以下N行每行一条日志，包含两个整数ts和id。
对于50%的数据，1 <= K <= N <= 1000
对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
【输出格式】
按从小到大的顺序输出热帖id。每个id一行。
【输入样例】
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
【输出样例】
1
3
代码及解决思路过程
import java.util.*;
/**
* 在ts时刻，编号id收到1个赞
* 一个帖子只要在任意一个D时间内有过>=k个赞 ==》热帖
* 从小到大顺序输出热帖id
* N=7 D=10 K=2
*/
public class 日志统计 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt(),d=scanner.nextInt(),k= scanner.nextInt();
int ts,id;
ArrayList <Integer> [] arr= new ArrayList[100001];//数组型容器
HashMap <Integer,Integer> hm = new HashMap<Integer,Integer>();//键值对
TreeSet <Integer> trs = new TreeSet<>();//去重并自动排序
//初始化arr 不然装不进去东西
for (int i=0;i<arr.length;i++) {
arr[i] = new ArrayList<>();
}
for (int i=0;i<n;i++) {
ts= scanner.nextInt();
id= scanner.nextInt();
arr[ts].add(id);
}
long star = System.currentTimeMillis();
for (int i=0;i<arr.length;i++) {
//在某个d时间段 id的赞超过k个，则此id被认为是热帖===>存进map中
/**
* 从0-d 时间段，对于id的增加是累加的
* 超过（题目大于等于）d这个时间，id的赞 会继续累加，但是它前面的已经不在这个新d范围，需要减掉 比如i==11的时候，需要减去i=i-d==1时候的id赞
*/
//遍历所有的 ts对应的容器
// System.out.println(arr[i]);
if(i>=d) { //从d开始扔掉前面的所有数据，使始终只剩下d个数据， d始终是个动态区间，扔到d区间之前的数据
for (Integer ids:arr[i-d]) {//i-d是动态去除i-d之前所有的数据，使剩下的数据只有区间d
if(hm.get(ids)>=k) {
trs.add(ids);//自动去重且自动排序
}
hm.put(ids,hm.get(ids)-1);
}
}
for (Integer ids : arr[i]) { //输出秒数ts对应的id,看懂这个关键在于i-d i-d==》退出d之前的，比如i==11 退出ts=i-d=1,时的id次数
//遍历有数据的ts对应的id
// System.out.println(ids);
/** 输入 7 10 2
* ts ids
* 0 [1,10]
* 9 [1]
* 10 [10,1]
* 100 [3,3]
*/
if(hm.containsKey(ids)) { //如果hashmap中有这个帖子id，点赞数+1
hm.put(ids,hm.get(ids)+1);
}else { //如果hashmap中没有这个帖子id，存进去
hm.put(ids,1);
}
}
}
for (Integer tr : trs) {
System.out.println(tr);
}
long end = System.currentTimeMillis();
//System.out.println(end-star);
}
}
评论区