Acwing 1238.日志统计 双指针

2024-03-30 18:28
文章标签 统计 指针 日志 acwing 1238

本文主要是介绍Acwing 1238.日志统计 双指针,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志,日志共有 N� 行。

其中每一行的格式是:

ts id  

表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞,小明就认为这个帖子曾是”热帖”。

具体来说,如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是”热帖”。

给定日志,请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式

第一行包含三个整数 N,D,K

以下 N�行每行一条日志,包含两个整数 ts和 id。

输出格式

按从小到大的顺序输出热帖 id

每个 id 占一行。

数据范围

1≤K≤N≤1051≤105,
0≤ts,id≤1050≤,≤105,
1≤D≤100001≤≤10000

输入样例:
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例:
1
3
思路:

因为统计一定时间内是否有效,因此我们首先按照时间顺序将输入序列排序。我们使用数组id记录每个id的帖子被点赞的次数,当次数大于k时,我们将相对应的t数组下标元素改变为true,说明该id的帖子达到要求。

但是我们在考虑次数时还要考虑时间的连续性。这也是我们使用双指针的原因,维护一个区间使得该区间内的时间维持在d时间中。如果超出,我们就需要对超出部分元素的次数减1(这里可能不好理解,这个-1能进行是因为这个区间是从前向后遍历的,并且已经按照时间顺序排序。如果之前有元素超出了并且已经>=k,我们-1后不影响t数组的结果。也就是说只保留局部结果)同时将j++

代码:
package lanqiao;import java.util.*;
public class Main{public static void main(String[] args) {int[] id = new int[100000];boolean[] t = new boolean[100000];Scanner sc = new Scanner(System.in);int n = sc.nextInt();int d = sc.nextInt();int k = sc.nextInt();int[][] arr = new int[n][2];for (int i = 0; i < n; i++) {int i1 = sc.nextInt();int i2 = sc.nextInt();arr[i] = new int[]{i1,i2};}sc.close();Arrays.sort(arr,(a,b) -> (a[0] - b[0]));List<Integer> ans = new ArrayList<>();for (int i = 0, j =0; i < n; i++) {id[arr[i][1]]++;while(arr[i][0] - arr[j][0] >= d){id[arr[j][1]]--;j++;}if(id[arr[i][1]] >= k) t[arr[i][1]] = true;}for (int i = 0; i < t.length; i++) {if(t[i]) System.out.println(i);}}
}

这篇关于Acwing 1238.日志统计 双指针的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/862243

相关文章

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.

如何自定义Nginx JSON日志格式配置

《如何自定义NginxJSON日志格式配置》Nginx作为最流行的Web服务器之一,其灵活的日志配置能力允许我们根据需求定制日志格式,本文将详细介绍如何配置Nginx以JSON格式记录访问日志,这种... 目录前言为什么选择jsON格式日志?配置步骤详解1. 安装Nginx服务2. 自定义JSON日志格式各

SpringBoot项目使用MDC给日志增加唯一标识的实现步骤

《SpringBoot项目使用MDC给日志增加唯一标识的实现步骤》本文介绍了如何在SpringBoot项目中使用MDC(MappedDiagnosticContext)为日志增加唯一标识,以便于日... 目录【Java】SpringBoot项目使用MDC给日志增加唯一标识,方便日志追踪1.日志效果2.实现步

SQL Server清除日志文件ERRORLOG和删除tempdb.mdf

《SQLServer清除日志文件ERRORLOG和删除tempdb.mdf》数据库再使用一段时间后,日志文件会增大,特别是在磁盘容量不足的情况下,更是需要缩减,以下为缩减方法:如果可以停止SQLSe... 目录缩减 ERRORLOG 文件(停止服务后)停止 SQL Server 服务:找到错误日志文件:删除

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中,我们都清楚统计信息对于优化器来说非常重要。一般情况下,我们会开启"自动更新

grom设置全局日志实现执行并打印sql语句

《grom设置全局日志实现执行并打印sql语句》本文主要介绍了grom设置全局日志实现执行并打印sql语句,包括设置日志级别、实现自定义Logger接口以及如何使用GORM的默认logger,通过这些... 目录gorm中的自定义日志gorm中日志的其他操作日志级别Debug自定义 Loggergorm中的

解决java.lang.NullPointerException问题(空指针异常)

《解决java.lang.NullPointerException问题(空指针异常)》本文详细介绍了Java中的NullPointerException异常及其常见原因,包括对象引用为null、数组元... 目录Java.lang.NullPointerException(空指针异常)NullPointer

SpringBoot项目注入 traceId 追踪整个请求的日志链路(过程详解)

《SpringBoot项目注入traceId追踪整个请求的日志链路(过程详解)》本文介绍了如何在单体SpringBoot项目中通过手动实现过滤器或拦截器来注入traceId,以追踪整个请求的日志链... SpringBoot项目注入 traceId 来追踪整个请求的日志链路,有了 traceId, 我们在排

Spring Boot整合log4j2日志配置的详细教程

《SpringBoot整合log4j2日志配置的详细教程》:本文主要介绍SpringBoot项目中整合Log4j2日志框架的步骤和配置,包括常用日志框架的比较、配置参数介绍、Log4j2配置详解... 目录前言一、常用日志框架二、配置参数介绍1. 日志级别2. 输出形式3. 日志格式3.1 PatternL